Abstract
We present a semidefinite programming approach to bound the measures of cross-independent pairs in a bipartite graph. This can be viewed as a far-reaching extension of Hoffman’s ratio bound on the independence number of a graph. As an application, we solve a problem on the maximum measures of cross-intersecting families of subsets with two different product measures, which is a generalized measure version of the Erdős–Ko–Rado theorem for cross-intersecting families with different uniformities.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Borg, P.: Cross-intersecting integer sequences. Preprint. ar**v:1212.6965
Delsarte, P.: An algebraic approach to the association schemes of coding theory. Phillips Research Reports Supplements issue no.10. N.V. Philips’ Gloeilampenfabrieken (1973)
Deza, M., Frankl, P.: Erdős–Ko–Rado theorem—22 years years later. SIAM J. Algebr. Discret. Methods 4, 419–431 (1983)
Erdős, P., Ko, C., Rado, R.: Intersection theorems for systems of finite sets. Q. J. Math. Oxf. Ser. (2) 12 313–320 (1961)
Fishburn, P.C., Frankl, P., Freed, D., Lagarias, J.C., Odlyzko, A.M.: Probabilities for intersecting systems and random subsets of finite sets. SIAM J. Algebr. Discret. Methods 7, 73–79 (1986)
Frankl, P., Graham, R.L.: Old and new proofs of the Erdős–Ko–Rado theorem. Sichuan Daxue Xuebao 26, 112–122 (1989)
Frankl, P., Tokushige, N.: Weighted multiply intersecting families. Stud. Sci. Math. Hung. 40, 287–291 (2003)
Friedgut, E.: On the measure of intersecting families, uniqueness and stability. Combinatorica 28, 503–528 (2008)
Gärtner, B., Matoušek, J.: Approximation Algorithms and Semidefinite Programming. Springer, Heidelberg (2012)
Godsil, C., Meagher, K.: Erdős–Ko–Rado Theorems: Algebraic Approaches. Cambridge University Press, Cambridge (2015)
Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979)
Matsumoto, M., Tokushige, N.: The exact bound in the Erdős–Ko–Rado theorem for cross-intersecting families. J. Comb. Theory Ser. A 52, 90–97 (1989)
Pyber, L.: A new generalization of the Erdős–Ko–Rado theorem. J. Comb. Theory Ser. A 43, 85–90 (1986)
Schrijver, A.: A comparison of the Delsarte and Lovász bounds. IEEE Trans. Inf. Theory 25, 425–429 (1979)
Suda, S., Tanaka, H.: A cross-intersection theorem for vector spaces based on semidefinite programming. Bull. Lond. Math. Soc. 46, 342–348 (2014). ar**v:1304.5466
Todd, M.J.: Semidefinite optimization. Acta Numer. 10, 515–560 (2001)
Tokushige, N.: Intersecting families—uniform versus weighted. Ryukyu Math. J. 18, 89–103 (2005)
Tokushige, N.: On cross \(t\)-intersecting families of sets. J. Comb. Theory Ser. A 117, 1167–1177 (2010)
Tokushige, N.: The eigenvalue method for cross \(t\)-intersecting families. J. Algebr. Comb. 38, 653–662 (2013)
Tokushige, N.: Cross \(t\)-intersecting integer sequences from weighted Erdős–Ko–Rado. Comb. Probab. Comput. 22, 622–637 (2013)
Wilson, R.M.: The exact bound in the Erdős–Ko–Rado theorem. Combinatorica 4, 247–257 (1984)
Acknowledgements
The authors thank Peter Frankl for telling them the reference [5]. They also thank the anonymous referees for comments and suggestions. Hajime Tanaka was supported by JSPS KAKENHI Grant No. 25400034. Norihide Tokushige was supported by JSPS KAKENHI Grant No. 25287031.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Suda, S., Tanaka, H. & Tokushige, N. A semidefinite programming approach to a cross-intersection problem with measures. Math. Program. 166, 113–130 (2017). https://doi.org/10.1007/s10107-016-1106-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-016-1106-3
Keywords
- The Erdős–Ko–Rado theorem
- Intersection theorem
- Cross-intersecting families
- Semidefinite programming
- Measure