Note on the number of antichains in generalizations of the Boolean lattice

Abstract

We give a short and self-contained argument that shows that, for any positive integers $t$ and $n$ with $t=O\left(\frac{n}{\log n}\right)$, the number $\alpha ([t{]}^n)$ of antichains of the poset $[t{]}^n$ is at most \[\exp_2\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\,,\] 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\to \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α([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$.

13 pages, 1 figure