The structure of large intersecting families

Kostochka, Alexandr; Mubayi, Dhruv

doi:10.1090/proc/13390

The structure of large intersecting families
HTML articles powered by AMS MathViewer

by Alexandr Kostochka and Dhruv Mubayi PDF

Proc. Amer. Math. Soc. 145 (2017), 2311-2321 Request permission

Abstract:

A collection of sets is intersecting if every two members have nonempty intersection. We describe the structure of intersecting families of $r$-sets of an $n$-set whose size is quite a bit smaller than the maximum ${n-1 \choose r-1}$ given by the Erdős-Ko-Rado Theorem. In particular, this extends the Hilton-Milner theorem on nontrivial intersecting families and answers a recent question of Han and Kohayakawa for large $n$. In the case $r=3$ we describe the structure of all intersecting families with more than 10 edges. We also prove a stability result for the Erdős matching problem. Our short proofs are simple applications of the Delta-system method introduced and extensively used by Frankl since 1977.

References

B. Bollobás, D. E. Daykin, and P. Erdős, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. (2) 27 (1976), no. 105, 25–32. MR 412030, DOI 10.1093/qmath/27.1.25
P. Erdős, A problem on independent $r$-tuples, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 8 (1965), 93–95. MR 260599
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
P. Erdős and L. Lovász, Problems and results on $3$-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627. MR 0382050
P. Erdös and R. Rado, A combinatorial theorem, J. London Math. Soc. 25 (1950), 249–255. MR 37886, DOI 10.1112/jlms/s1-25.4.249
Péter Frankl, On families of finite sets no two of which intersect in a singleton, Bull. Austral. Math. Soc. 17 (1977), no. 1, 125–134. MR 457226, DOI 10.1017/S0004972700025521
Péter Frankl, On intersecting families of finite sets, J. Combinatorial Theory Ser. A 24 (1978), no. 2, 146–161. MR 480051, DOI 10.1016/0097-3165(78)90003-1
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, Improved bounds for Erdős’ matching conjecture, J. Combin. Theory Ser. A 120 (2013), no. 5, 1068–1072. MR 3033661, DOI 10.1016/j.jcta.2013.01.008
P. Frankl, On the maximum number of edges in a hypergraph with given matching number, arXiv:1205.6847.
Zoltán Füredi, Linear trees in uniform hypergraphs, European J. Combin. 35 (2014), 264–272. MR 3090501, DOI 10.1016/j.ejc.2013.06.022
Zoltán Füredi and Tao Jiang, Hypergraph Turán numbers of linear cycles, J. Combin. Theory Ser. A 123 (2014), 252–270. MR 3157810, DOI 10.1016/j.jcta.2013.12.009
J. Han and Y. Kohayakawa, The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family, arXiv:1509.05464.
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
Hao Huang, Po-Shen Loh, and Benny Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21 (2012), no. 3, 442–450. MR 2912790, DOI 10.1017/S096354831100068X
Tomasz Łuczak and Katarzyna Mieczkowska, On Erdős’ extremal problem on matchings in hypergraphs, J. Combin. Theory Ser. A 124 (2014), 178–194. MR 3176196, DOI 10.1016/j.jcta.2014.01.003