Infinite Sperner's theorem

DOI10.1016/J.JCTA.2021.105558MaRDI QIDQ2068601zbMATH OpenOpenAlexWikidataFDO

Authors István Tomon, Adam Zsolt Wagner, Benny Sudakov

Publication date 20 January 2022

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2008.04804

zbMATH Keywords

antichainsSperner theoremprefix codes

Mathematics Subject Classification ID

Prefix, length-variable, comma-free codes (94A45) Extremal set theory (05D05)

Abstract: One of the most classical results in extremal set theory is Sperner's theorem, which says that the largest antichain in the Boolean lattice $2^{[n]}$ has size $$. Motivated by an old problem of ErdH{o}s on the growth of infinite Sidon sequences, in this note we study the growth rate of maximum infinite antichains. Using the well known Kraft's inequality for prefix codes, it is not difficult to show that infinite antichains should be "thinner" than the corresponding finite ones. More precisely, if $mathcalFsubset{2}^{mathbbN}$ is an antichain, then ${\displaystyle }$liminf_{n ightarrow infty}�ig|mathcal{F} cap 2^{[n]}�ig|left(frac{2^n}{nlog n} ight)^{-1}=0.${\displaystyle }$ Our main result shows that this bound is essentially tight, that is, we construct an antichain $mathcalF$ such that ${\displaystyle }$liminf_{n ightarrow infty}�ig|mathcal{F} cap 2^{[n]}�ig|left(frac{2^n}{nlog^{C} n} ight)^{-1}>0${\displaystyle }$ holds for some absolute constant $C>0$.

Recommendations

• A Note on Infinite Antichain Density
• scientific article; zbMATH DE number 3871364
• A random version of Sperner's theorem
• scientific article; zbMATH DE number 937456
• Sperner's theorem and a problem of Erdős, Katona and Kleitman

Cites work

• scientific article; zbMATH DE number 53676 (Why is no real title available?)
• scientific article; zbMATH DE number 6319745 (Why is no real title available?)
• scientific article; zbMATH DE number 3111990 (Why is no real title available?)
• A problem of arrangements
• An infinite Sidon sequence
• Infinite Sidon sets contained in sparse random sets of integers
• On a Problem of Sidon in Additive Number Theory and on Some Related Problems Addendum
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On strong Sidon sets of integers
• Short proofs of some extremal results. III
• The cycle lemma and some applications

Cited in

(7)

• A Note on Infinite Antichain Density
• scientific article; zbMATH DE number 4075524 (Why is no real title available?)
• An infinitary version of the Graham-Leeb-Rothschild theorem
• scientific article; zbMATH DE number 3931779 (Why is no real title available?)
• scientific article; zbMATH DE number 4196578 (Why is no real title available?)
• scientific article; zbMATH DE number 2216156 (Why is no real title available?)
• The width of downsets

This page was built for publication: Infinite Sperner's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2068601)