Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-12T06:57:52.573Z Has data issue: false hasContentIssue false
  • English
  • Français

Sperner's Theorem and a Problem of Erdős, Katona and Kleitman

Published online by Cambridge University Press:  01 December 2014

SHAGNIK DAS,
WENYING GAN and
BENNY SUDAKOV
SHAGNIK DAS
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: shagnik@ucla.edu, wgan@math.ucla.edu)
WENYING GAN
Affiliation:
Department of Mathematics, UCLA, Los Angeles, CA 90095, USA (e-mail: shagnik@ucla.edu, wgan@math.ucla.edu)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, ETH, 8092 Zürich, Switzerland (e-mail: benjamin.sudakov@math.ethz.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A central result in extremal set theory is the celebrated theorem of Sperner from 1928, which gives the size of the largest family of subsets of [n] not containing a 2-chain, F1 ⊂ F2. Erdős extended this theorem to determine the largest family without a k-chain, F1 ⊂ F2 ⊂ . . . ⊂ Fk. Erdős and Katona, followed by Kleitman, asked how many chains must appear in families with sizes larger than the corresponding extremal bounds.

In 1966, Kleitman resolved this question for 2-chains, showing that the number of such chains is minimized by taking sets as close to the middle level as possible. Moreover, he conjectured the extremal families were the same for k-chains, for all k. In this paper, making the first progress on this problem, we verify Kleitman's conjecture for the families whose size is at most the size of the k + 1 middle levels. We also characterize all extremal configurations.

Keywords

Primary 05D05

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 24 , Special Issue 4: Oberwolfach Special Issue Part 1 , July 2015, pp. 585 - 608
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Chung, F. R. K., Füredi, Z., Graham, R. L. and Seymour, P. (1988) On induced subgraphs of the cube. J. Combin. Theory Ser. A 49 180–187.CrossRefGoogle Scholar
[2]Das, S., Gan, W. and Sudakov, B. (2014) The minimum number of disjoint pairs in set systems and related problems. Combinatorica, to appear.Google Scholar
[3]Dove, A. P., Griggs, J. R., Kang, R. J. and Sereni, J. S. (2014) Supersaturation in the Boolean lattice. Integers 14A 1–7.Google Scholar
[4]Engel, K. (1997) Sperner Theory, Cambridge University Press.CrossRefGoogle Scholar
[5]Erdős, P. (1945) On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc. 51 898–902.CrossRefGoogle Scholar
[6]Erdős, P. (1962) On a theorem of Rademacher–Turán. Illinois J. Math. 6 122–127.CrossRefGoogle Scholar
[7]Erdős, P. (1962) On the number of complete subgraphs contained in certain graphs. Magy. Tud. Acad. Mat. Kut. Int. Közl. 7 459–474.Google Scholar
[8]Erdős, P. and Kleitman, D. (1974) Extremal problems among subsets of a set. Discrete Math. 8 281–294.CrossRefGoogle Scholar
[9]Katona, G. O. H. and Tarján, T. G. (1983) Extremal problems with excluded subgraphs in the n-cube. In Graph Theory (Borowiecki, M.et al., eds), Vol. 1018 of Lecture Notes in Mathematics, Springer, pp. 84–93.Google Scholar
[10]Kleitman, D. (1966) A conjecture of Erdős–Katona on commensurable pairs among subsets of an n-set. In Theory of Graphs: Proc. Colloq. Tihany, pp. 215–218.Google Scholar
[11]Mantel, W. (1907) Problem 28. Wiskundige Opgaven 10 60–61.Google Scholar
[12]Qian, J., Engel, K. and Xu, W. (2009) A generalization of Sperner's theorem and an application to graph orientations. Discrete Appl. Math. 157 2170–2176.CrossRefGoogle Scholar
[13]Sperner, E. (1928) Ein Satz über Untermengen einer endlichen Menge. Math. Z. 27 544–548.CrossRefGoogle Scholar