The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family

Han, Jie; Kohayakawa, Yoshiharu

doi:10.1090/proc/13221

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).