Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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


Authors: Jie Han and Yoshiharu Kohayakawa
Journal: Proc. Amer. Math. Soc. 145 (2017), 73-87
MSC (2010): Primary 05D05
DOI: https://doi.org/10.1090/proc/13221
Published electronically: June 30, 2016
MathSciNet review: 3565361
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1006/jcta.1996.0092
  • [2] 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, https://doi.org/10.1016/j.jcta.2007.03.010
  • [3] Peter Borg, Non-trivial intersecting uniform sub-families of hereditary families, Discrete Math. 313 (2013), no. 17, 1754-1761. MR 3061011, https://doi.org/10.1016/j.disc.2013.04.017
  • [4] Irit Dinur and Ehud Friedgut, Intersecting families are essentially contained in juntas, Combin. Probab. Comput. 18 (2009), no. 1-2, 107-122. MR 2497376, https://doi.org/10.1017/S0963548308009309
  • [5] 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 0140419
  • [6] Peter Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc. 21 (1980), no. 3, 363-372. MR 585195, https://doi.org/10.1017/S0004972700006225
  • [7] 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, https://doi.org/10.1016/0097-3165(87)90005-7
  • [8] 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 (88k:05007)
  • [9] P. Frankl and Z. Füredi, Nontrivial intersecting families, J. Combin. Theory Ser. A 41 (1986), no. 1, 150-153. MR 826944, https://doi.org/10.1016/0097-3165(86)90121-4
  • [10] 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, https://doi.org/10.1016/0097-3165(92)90054-X
  • [11] 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
  • [12] 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 0219428
  • [13] 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).
  • [14] Tao Jiang, personal communication, Nov 2015.
  • [15] Peter Keevash, Shadows and intersections: stability and new proofs, Adv. Math. 218 (2008), no. 5, 1685-1703. MR 2419936, https://doi.org/10.1016/j.aim.2008.03.023
  • [16] Peter Keevash and Dhruv Mubayi, Set systems without a simplex or a cluster, Combinatorica 30 (2010), no. 2, 175-200. MR 2676834, https://doi.org/10.1007/s00493-010-2401-x
  • [17] Alexandr Kostochka and Dhruv Mubayi, The structure of large intersecting families, arXiv:1602.01391 (2016).

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05D05

Retrieve articles in all journals with MSC (2010): 05D05


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
Email: yoshi@ime.usp.br

DOI: https://doi.org/10.1090/proc/13221
Keywords: Intersecting families, Hilton--Milner theorem, Erd\H{o}s--Ko--Rado theorem
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
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society