Subsets of posets minimising the number of chains
HTML articles powered by AMS MathViewer
- by Wojciech Samotij PDF
- Trans. Amer. Math. Soc. 371 (2019), 7259-7274 Request permission
Abstract:
A well-known theorem of Sperner describes the largest collections of subsets of an $n$-element set, none of which contain another set from the collection. Generalising this result, Erdős characterised the largest families of subsets of an $n$-element set that do not contain a chain of sets $A_1 \subset \cdots \subset A_k$ of an arbitrary length $k$. The extremal families contain all subsets whose cardinalities belong to an interval of length $k-1$ centred at $n/2$. In a far-reaching extension of Sperner’s theorem, Kleitman determined the smallest number of chains of length $2$ that have to appear in a collection of a given number $a$ of subsets of an $n$-element set. For every $a$, this minimum is achieved by the collection comprising $a$ sets whose cardinalities are as close to $n/2+1/4$ as possible. We show that the same is true about chains of an arbitrary length $k$, for all $a$ and $n$, confirming the prediction Kleitman made $50$ years ago. We also characterise all families of $a$ subsets with the smallest number of chains of length $k$ for all $a$ for which this smallest number is positive. Our argument is inspired by an elegant probabilistic lemma from a recent paper of Noel, Scott, and Sudakov, which in turn can be traced back to Lubell’s proof of Sperner’s theorem.References
- J. Balogh, S. Petříčková, and A. Z. Wagner, Families in posets minimizing the number of comparable pairs, arXiv:1703.05427 [math.CO] (2017).
- József Balogh and Adam Zsolt Wagner, Kleitman’s conjecture about families of given size minimizing the number of $k$-chains, Adv. Math. 330 (2018), 229–252. MR 3787545, DOI 10.1016/j.aim.2018.03.007
- Shagnik Das, Wenying Gan, and Benny Sudakov, Sperner’s theorem and a problem of Erdős, Katona and Kleitman, Combin. Probab. Comput. 24 (2015), no. 4, 585–608. MR 3350024, DOI 10.1017/S0963548314000273
- Andrew P. Dove, Jerrold R. Griggs, Ross J. Kang, and Jean-Sébastien Sereni, Supersaturation in the Boolean lattice, Integers 14A (2014), Paper No. A4, 7. MR 3226565
- P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI 10.1090/S0002-9904-1945-08454-7
- D. Kleitman, A conjecture of Erdős-Katona on commensurable pairs among subsets of an $n$-set, Theory of Graphs (Proc. Colloq., Tihany, 1966) Academic Press, New York, 1968, pp. 215–218. MR 0232685
- J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III, Rec. Math. [Mat. Sbornik] N.S. 12(54) (1943), 277–286 (English, with Russian summary). MR 0009656
- D. Lubell, A short proof of Sperner’s lemma, J. Combinatorial Theory 1 (1966), 299. MR 194348
- Jonathan A. Noel, Alex Scott, and Benny Sudakov, Supersaturation in posets and applications involving the container method, J. Combin. Theory Ser. A 154 (2018), 247–284. MR 3718067, DOI 10.1016/j.jcta.2017.08.019
- Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), no. 1, 544–548 (German). MR 1544925, DOI 10.1007/BF01171114
Additional Information
- Wojciech Samotij
- Affiliation: School of Mathematical Sciences, Tel Aviv University, Tel Aviv 6997801, Israel
- MR Author ID: 871997
- Email: samotij@post.tau.ac.il
- Received by editor(s): November 27, 2017
- Received by editor(s) in revised form: March 3, 2018
- Published electronically: October 18, 2018
- Additional Notes: Research was supported in part by Israel Science Foundation grant 1147/14.
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 7259-7274
- MSC (2010): Primary 05D99, 06A07; Secondary 05D40
- DOI: https://doi.org/10.1090/tran/7601
- MathSciNet review: 3939577