Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-23T23:52:41.383Z Has data issue: false hasContentIssue false

On the union of intersecting families

Published online by Cambridge University Press:  27 June 2019

David Ellis*
Affiliation:
School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London, E1 4NS, UK
Noam Lifshitz
Affiliation:
Einstein Institute of Mathematics, Edmond J. Safra Campus, Hebrew University of Jerusalem, Givat Ram, Jerusalem 9190401, Israel
*
*Corresponding author. Email: [email protected]

Abstract

A family of sets is said to be intersecting if any two sets in the family have non-empty intersection. In 1973, Erdős raised the problem of determining the maximum possible size of a union of r different intersecting families of k-element subsets of an n-element set, for each triple of integers (n, k, r). We make progress on this problem, proving that for any fixed integer r ⩾ 2 and for any $$k \le ({1 \over 2} - o(1))n$$, if X is an n-element set, and $${\cal F} = {\cal F}_1 \cup {\cal F}_2 \cup \cdots \cup {\cal F}_r $$, where each $$ {\cal F}_i $$ is an intersecting family of k-element subsets of X, then $$|{\cal F}| \le \left( {\matrix{n \cr k \cr } } \right) - \left( {\matrix{{n - r} \cr k \cr } } \right)$$, with equality only if $${\cal F} = \{ S \subset X:|S| = k,\;S \cap R \ne \emptyset \} $$ for some RX with |R| = r. This is best possible up to the size of the o(1) term, and improves a 1987 result of Frankl and Füredi, who obtained the same conclusion under the stronger hypothesis $$k < (3 - \sqrt 5 )n/2$$, in the case r = 2. Our proof utilizes an isoperimetric, influence-based method recently developed by Keller and the authors.

MSC classification

Type
Paper
Copyright
© Cambridge University Press 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ahlswede, R. and Katona, G. O. (1977) Contributions to the geometry of Hamming spaces. Discrete Math. 17 122.CrossRefGoogle Scholar
Bollobás, B. (1986) Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge University Press.Google Scholar
Bollobás, B., Daykin, D. E. and Erd˝os, P. (1976) Sets of independent edges of a hypergraph. Quart. J. Math. Oxford Ser. 2 27 2532.CrossRefGoogle Scholar
Ellis, D., Keller, N. and Lifshitz, N. (2016) Stability versions of Erd˝os–Ko–Rado type theorems, via isoperimetry. J. Eur. Math. Soc., to appear. arXiv:1604.02160Google Scholar
Ellis, D., Keller, N. and Lifshitz, N. (2019) On a biased edge isoperimetric inequality for the discrete cube. J. Combin. Theory Ser. A 163 118162.CrossRefGoogle Scholar
Erd˝os, P. (1965) A problem on independent r-tuples. Ann. Univ. Sci. Budapest 8 9395.Google Scholar
Erd˝os, P. (1976) Problems and results on finite and infinite combinatorial analysis. In Infinite and Finite Sets (Hajnal, A., Rado, R. and Sós, V. T., eds), Vol. 10 of Proc. Colloq. Math. Soc. J. Bolyai (Keszthely, Hungary, 1973), pp. 403424, Bolyai–North-Holland.Google Scholar
Erd˝os, P., Ko, C. and Rado, R. (1961) Intersection theorems for systems of finite sets. Quart. J. Math. Oxford, Ser. 2 12 313320.CrossRefGoogle Scholar
Fortuin, C. M., Kasteleyn, P. W. and Ginibre, J. (1971) Correlation inequalities on some partially ordered sets. Commun. Math. Phys. 22 89103.CrossRefGoogle Scholar
Frankl, P. (1987) Erd˝os–Ko–Rado theorem with conditions on the maximal degree. J. Combin. Theory Ser. A 46 252263.CrossRefGoogle Scholar
Frankl, P. (2013) Improved bounds for Erd˝os’ Matching Conjecture. J. Combin. Theory Ser. A 120 10681072.CrossRefGoogle Scholar
Frankl, P. and Füredi, Z. (1986) Extremal problems concerning Kneser graphs. J. Combin. Theory Ser. B 40 270285.CrossRefGoogle Scholar
Frankl, P. and Kupavskii, A. (2018) The Erd˝os Matching Conjecture and concentration inequalities. arXiv:1806.08855Google Scholar
Harris, T. E. (1960) A lower bound for the critical probability in a certain percolation. Math. Proc. Camb. Phil. Soc. 56 1320.CrossRefGoogle Scholar
Huang, H., Loh, P. and Sudakov, B. (2012) The size of a hypergraph and its matching number. Combin. Probab. Comput. 21 442450.CrossRefGoogle Scholar
Kahn, J. and Kalai, G. (2007) Thresholds and expectation thresholds. Combin. Probab. Comput. 16 495502.CrossRefGoogle Scholar
Kleitman, D. J. 1966) Families of non-disjoint subsets. J. Combin. Theory 1 153155.CrossRefGoogle Scholar
Russo, L. (1982) An approximate zero-one law. Z. Wahrsch. Verw. Gebiete 61 129139.CrossRefGoogle Scholar