Abstract
Let \(n, \ell\) be positive integers, \(n > 2\ell + 1\). Let X be an n-element set and \(\mathcal{F}\) an antichain, \(\mathcal{F} \subset 2^X\). Kiselev, Kupavskii and Patkós conjectured that if \(|F\cup G| \leq 2\ell + 1\) for all \(F, G \in \mathcal{F}\) then the minimum degree of \(\mathcal{F}\) is no more than \({n - 1\choose \ell - 1}\), the minimum degree of \({[n]\choose \ell}\). We prove this conjecture for \(n \geq \ell^3 + \ell^2 + \frac32 \ell\) and solve the analogous problem for the case \(|F \cap G| \geq t\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford, Ser. (2), 12 (1961), 313–320.
Frankl, P.: Generalizations of theorems of Katona and Milner. Acta Math. Acad. Sci. Hungar. 27, 359–363 (1976)
P. Frankl, The shifting technique in extremal set theory, in: Surveys in Combinatorics, London Math. Soc. Lecture Note Ser. 123, Cambridge Univ. Press (Cambridge, 1987), 81–110
Frankl, P.: Shadows and shifting. Graphs Combin. 7, 23–29 (1991)
Frankl, P.: Antichains of fixed diameter. Moscow J. Combin. Number Theory 7, 189–219 (2017)
Frankl, P.: Maximum degree and diversity in intersecting hypergraphs. J. Combin. Theory Ser. B 144, 81–94 (2020)
P. Frankl and A. Kupavskii, Diversity, arXiv:1811.01111
Hao, H.: Two extremal problems on intersecting families. European J. Combin. 76, 1–9 (2019)
Huang, H., Zhao, Y.: Degree versions of the Erdős-Ko-Rado Theorem and Erdős hypergraph matching conjecture. J. Combin. Theory Ser. A 150, 233–247 (2017)
Katona, G.O.H.: Intersection theorems for systems of finite sets. Acta Math. Acad. Sci. Hungar. 15, 329–337 (1964)
G. O. H. Katona, A theorem of finite sets, in: Theory of Graphs, Proc. Colloq. Tihany, 1966, Akadémiai Kiadó (Budapest, 1968), pp. 187–207,
J. B. Kruskal, The number of simplices in a complex, in: Math. Optimization Techniques, Univ. of Calif. Press (Berkeley, 1963), pp. 251–278
Kupavskii, A.: Diversity of uniform intersecting families. European J. Combin. 74, 39–47 (2018)
Kupavskii, A.: Degree versions of theorems on intersecting families via stability. J. Combin. Theory Ser. A 168, 272–287 (2019)
S. Kiselev, A. Kupavskii and B. Patkós, Personal communication, 2020
Kupavskii, A., Zakharov, D.: Regular bipartite graphs and intersecting families. J. Combin. Theory Ser. A 155, 180–189 (2018)
Milner, E.C.: A combinatorial theorem on systems of sets. J. London Math. Soc. 43, 204–206 (1968)
Sperner, E.: Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27, 544–548 (1928)
Acknowledgements
The author is indebted to Andrey Kupavskii for telling him about Conjecture 1.3.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by the Ministry of Education and Science of the Russian Federation in the framework of MegaGrant no. 075-15-2019-1926.
Rights and permissions
About this article
Cite this article
Frankl, P. Minimum degree and diversity in intersecting antichains. Acta Math. Hungar. 163, 652–662 (2021). https://doi.org/10.1007/s10474-020-01100-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-020-01100-y