Combinatorial Theory

We give a short and self-contained argument that shows that, for any positive integers \(t\) and \(n\) with \(t =O\Bigl(\frac{n}{\log n}\Bigr)\), the number \(\alpha([t]^n)\) of antichains of the poset \([t]^n\) is at most \[{\exp_2\Bigl[\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\Bigr]}\,,\] where \(N(t,n)\) is the size of a largest level of \([t]^n\). This, in particular, says that if \({t \!\ll\! n/\log^3 \! n}\) as \(n \rightarrow \infty\), then \(\log\alpha([t]^n)=(1+o(1))N(t,n)\), giving a (partially) positive answer to a question of Moshkovitz and Shapira for \(t, n\) in this range. Particularly for \(t=3\), we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of \([3]^n\).

Mathematics Subject Classifications: 05A16, 06A07

Keywords: Boolean lattice, antichains, entropy method