Number of largest antichains in Boolean poset.

554 Views Asked by At

Let $B_n$ be a boolean cube , i.e. $B_n = \{(a_1 \dots a_n), a_i \in \{0,1\}\}$. We want to describe largest antichain in this poset. Let's say that $a \le_{2} b$ iff $a_{i} \le b_{i}$ $\forall i \le n$. We may represent $B_n$ like a graph , where the bottom one point is $(0 \dots 0)$ and the highest one is $(1 \dots 1)$. And the edges only between neighbor layers ($a_k \le_2 b_{k+1}$, where $a_k \in V_k^n$ and $b_{k+1} \in V_{k+1}^n$).

First of all using if $c$ is antichain and $V^n_{k}$ is k-th layer of Boolean cube, then $\displaystyle \sum_{k = 0}^{n} \frac{|c_k|}{\binom{n}{k}} \le 1$, where $c_k = c \cap V_k^n$. That's just a LYM - inequality, so using this inequality and $\binom{n}{k} \le\binom{n}{n/2}$ we have that $|c| \le \binom{n}{n/2}$.

And the upper bound is reached by $V_{n/2}^n$. Now we need to determine number of such antichains. I guees there should be only $1$ or $2$ such antichains (depend of $n$). But how can we show this ? Also does my proof for maximal size is correct?

Edit. Sperner's theorem shows that's my first idea is correct. So the main problem to determine how many antichains of size $\binom{n}{n/2}$ could be in $B_n$.

1

There are 1 best solutions below

10
On BEST ANSWER

First assume $n$ is even. Then $\sum_{k=1}^n \frac{|c_k|}{{n \choose k}} \le 1$ and $\sum_{k=1}^n |c_k| = {n \choose n/2}$ imply that $c_{n/2} = {n \choose 2}$ and $c_j = 0$ for $j \not = n/2$. To see this implication, just note that ${n \choose n/2}$ is the largest binomial coefficient, so to minimize $\sum_{k=1}^n \frac{|c_k|}{{n \choose k}}$ given $\sum_{k=1}^n |c_k| = {n \choose n/2}$, you put all the mass of the $c_k$'s at $n/2$, and since doing this already achieves $\sum_{k=1}^n \frac{|c_k|}{n \choose k} = 1$, we know that any other distribution will yield $\sum_{k=1}^n \frac{|c_k|}{n \choose k} > 1$ (since ${n \choose k}$ is strictly less than ${n \choose n/2}$ for $k \not = n/2$). Hence, there is only one antichain of size $\frac{n}{2}$.

The analogous argument for $n$ odd shows that the total mass of $\{c_k\}_k$ is supported on $\frac{n-1}{2}$ and $\frac{n+1}{2}$. So the question is how many antichains there can be with all elements in $V_{(n-1)/2}^n$ or $V_{(n+1)/2}^n$. It's well known that there are only 2 such antichains, either all of $V_{(n-1)/2}^n$ or all of $V_{(n+1)/2}^n$. For a reference of this well-known result, first notice that this whole boolean setup is obviously isomorphic to the poset of subsets of $\{1,\dots,n\}$, ordered by inclusion. See the very bottom of page 7 until the very top of page 10.

https://courses.maths.ox.ac.uk/node/view_material/42883