The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family
HTML articles powered by AMS MathViewer
- by Jie Han and Yoshiharu Kohayakawa PDF
- Proc. Amer. Math. Soc. 145 (2017), 73-87 Request permission
Abstract:
The celebrated Erdős–Ko–Rado theorem determines the maximum size of a $k$-uniform intersecting family. The Hilton–Milner theorem determines the maximum size of a $k$-uniform intersecting family that is not a subfamily of the so-called Erdős–Ko–Rado family. In turn, it is natural to ask what the maximum size of an intersecting $k$-uniform family that is neither a subfamily of the Erdős–Ko–Rado family nor of the Hilton–Milner family is. For $k\ge 4$, this was solved (implicitly) in the same paper by Hilton–Milner in 1967. We give a different and simpler proof, based on the shifting method, which allows us to solve all cases $k\ge 3$ and characterize all extremal families achieving the extremal value.References
- Rudolf Ahlswede and Levon H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory Ser. A 76 (1996), no. 1, 121–138. MR 1405994, DOI 10.1006/jcta.1996.0092
- József Balogh and Dhruv Mubayi, A new short proof of a theorem of Ahlswede and Khachatrian, J. Combin. Theory Ser. A 115 (2008), no. 2, 326–330. MR 2382520, DOI 10.1016/j.jcta.2007.03.010
- Peter Borg, Non-trivial intersecting uniform sub-families of hereditary families, Discrete Math. 313 (2013), no. 17, 1754–1761. MR 3061011, DOI 10.1016/j.disc.2013.04.017
- Irit Dinur and Ehud Friedgut, Intersecting families are essentially contained in juntas, Combin. Probab. Comput. 18 (2009), no. 1-2, 107–122. MR 2497376, DOI 10.1017/S0963548308009309
- P. Erdős, Chao Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320. MR 140419, DOI 10.1093/qmath/12.1.313
- Peter Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc. 21 (1980), no. 3, 363–372. MR 585195, DOI 10.1017/S0004972700006225
- Peter Frankl, Erdős-Ko-Rado theorem with conditions on the maximal degree, J. Combin. Theory Ser. A 46 (1987), no. 2, 252–263. MR 914659, DOI 10.1016/0097-3165(87)90005-7
- Peter Frankl, The shifting technique in extremal set theory, Surveys in combinatorics 1987 (New Cross, 1987) London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 81–110. MR 905277
- P. Frankl and Z. Füredi, Nontrivial intersecting families, J. Combin. Theory Ser. A 41 (1986), no. 1, 150–153. MR 826944, DOI 10.1016/0097-3165(86)90121-4
- Peter Frankl and Norihide Tokushige, Some best possible inequalities concerning cross-intersecting families, J. Combin. Theory Ser. A 61 (1992), no. 1, 87–97. MR 1178386, DOI 10.1016/0097-3165(92)90054-X
- Z. Füredi, Erdős-Ko-Rado type theorems with upper bounds on the maximum degree, Algebraic methods in graph theory, Vol. I, II (Szeged, 1978) Colloq. Math. Soc. János Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981, pp. 177–207. MR 642041
- A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 18 (1967), 369–384. MR 219428, DOI 10.1093/qmath/18.1.369
- Eliza Jackowska, Joanna Polcyn, and Andrzej Ruciński, Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three, ArXiv e-prints (2015).
- Tao Jiang, personal communication, Nov 2015.
- Peter Keevash, Shadows and intersections: stability and new proofs, Adv. Math. 218 (2008), no. 5, 1685–1703. MR 2419936, DOI 10.1016/j.aim.2008.03.023
- Peter Keevash and Dhruv Mubayi, Set systems without a simplex or a cluster, Combinatorica 30 (2010), no. 2, 175–200. MR 2676834, DOI 10.1007/s00493-010-2401-x
- Alexandr Kostochka and Dhruv Mubayi, The structure of large intersecting families, arXiv:1602.01391 (2016).
Additional Information
- Jie Han
- Affiliation: Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil
- Email: jhan@ime.usp.br
- Yoshiharu Kohayakawa
- Affiliation: Instituto de Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010, 05508-090, São Paulo, Brazil
- MR Author ID: 272202
- Email: yoshi@ime.usp.br
- Received by editor(s): September 17, 2015
- Received by editor(s) in revised form: February 6, 2016, and March 22, 2016
- Published electronically: June 30, 2016
- Additional Notes: The first author was supported by FAPESP (2014/18641-5, 2015/07869-8)
The second author was partially supported by FAPESP (2013/03447-6, 2013/07699-0), CNPq (459335/2014-6, 310974/2013-5 and 477203/2012-4) and the NSF (DMS 1102086)
The authors acknowledge the support of NUMEC/USP (Project MaCLinC/USP) - Communicated by: Patricia L. Hersh
- © Copyright 2016 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 73-87
- MSC (2010): Primary 05D05
- DOI: https://doi.org/10.1090/proc/13221
- MathSciNet review: 3565361