Google Research

A simple upper bound on the number of antichains in $[t]^n$

Order (2018)

Abstract

In this paper for $t>2$ and $n>2$, we give a simple upper bound on $a\left([t]^n\right)$, the number of antichains in chain product poset $[t]^n$. When $t=2$, the problem reduces to classical Dedekind's problem posed in 1897 and studied extensively afterwards. However few upper bounds have been proposed for $t>2$ and $n>2$. The new bound is derived with straightforward extension of bracketing decomposition used by Hansel for bound $3^{n\choose\lfloor n/2\rfloor}$ for classical Dedekind's problem. To our best knowledge, our new bound is the best when $\Theta\left(\left(\log_2t\right)^2\right)=\frac{6t^4\left(\log_2\left(t+1\right)\right)^2}{\pi\left(t^2-1\right)\left(2t-\frac{1}{2}\log_2\left(\pi t\right)\right)^2}$ is less than $n$ and $t=\omega\left(\frac{n^{1/8}}{\left(\log_2n\right)^{3/4}}\right)$.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work