3

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$.

openspace
  • 6,470
  • 1
    The number of maximal antichains is huge and difficult to compute. – Matt Samuel Oct 23 '19 at 16:53
  • @MattSamuel even in Boolean cube? – openspace Oct 23 '19 at 17:02
  • 1
    If you mean the power set boolean algebra, which I think you do, especially yes. Huge number of maximal antichains. – Matt Samuel Oct 23 '19 at 17:04
  • @MattSamuel I've added some explanation what I want to describe. And also maximal in your notation means that it has maximal size among all antichains? – openspace Oct 23 '19 at 17:13
  • Yes, this is the power set boolean algebra. It's certainly not true that the only maximal antichains are $V_{n/2}^n$. – Matt Samuel Oct 23 '19 at 17:16
  • Do you mean maximal as in you cannot add another node (subset), but it does not have to necessarily meet the ${n \choose n/2}$ size? Or do you mean maximum as in it has to have the ${n \choose n/2}$ size? – antkam Oct 23 '19 at 17:17
  • @antkam I mean maximum that has a maximal possible size. Or there can be larger than $\binom{n}{n/2}$ size? – openspace Oct 23 '19 at 17:19
  • The words "maximum" usually mean global and "maximal" usually means local, so we might have a confusion there. Anyway, @MattSamuel (I'm guessing) may be talking about the Dedekind numbers but I am not sure. In any case, if you want anti-chains of size ${n \choose n/2}$ then I think all your questions are directly answered by Sperner's Theorem – antkam Oct 23 '19 at 17:42
  • @antkam but Sperner's theorem shows upper bound for antichain size. – openspace Oct 23 '19 at 17:49
  • haha, sorry i lost track. Sperner's Theorem answered two of your questions: is ${n \choose n/2}$ biggest possible size? Yes. and: is your proof valid? Also Yes. it does not answer the question of how many. – antkam Oct 23 '19 at 18:05
  • What does $V_k^n$ stand for? – Mirko Oct 25 '19 at 00:57
  • @Mirko it's k-th layer of Boolean cube. And it's also means all binary string with $k$ $1'$s – openspace Oct 25 '19 at 06:31

1 Answers1

4

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

mathworker21
  • 34,399
  • Thanks for your proof, but I want it to be more strict. Actually I understand too that $\sum\frac{|c_k|}{\binom{n}{k}} = 1$ if all mass should be near the $k = n/2$. But I can't prove it strictly. So actually I'm interested in strict proof that $\sum \frac{|c_k|}{\binom{n}{n/2}} = 1$ and $\sum |c_k| = \binom{n}{n/2}$ iff $c_{n/2} = \binom{n}{n/2}$. – openspace Oct 26 '19 at 10:35
  • @openspace the general statement is: let $a_1 > a_2 > \dots > a_n$ be reals and $b_1,\dots,b_n$ be non-negative reals with $\sum_i b_i = k$; then, $\sum_i a_ib_i > ka_n$ unless $b_n = k$. the proof is that $a_1b_1+\dots+a_nb_n > a_nb_1+\dots+a_nb_n$ unless $b_1=\dots=b_{n-1} = 0$. is this good now? – mathworker21 Oct 26 '19 at 11:17
  • @mathworker21 - Actually I've been thinking about the last part for a few days without success, i.e. how to prove that the odd case implies either all of one layer or all of the other layer. Can you give a hint? – antkam Oct 26 '19 at 12:46
  • @antkam hmm, it actually is tricky. I didn't include it in the answer, because it's very standard and I thought it should be easy. The proof I know uses induction cleverly. – mathworker21 Oct 26 '19 at 13:11
  • @antkam also, I know this one is pretty outside your interests, but I'd be happy if you/anyone figured this out: https://math.stackexchange.com/questions/2747669/a-question-about-existence-of-a-continuous-function – mathworker21 Oct 26 '19 at 13:14
  • @mathworker21 if we order $a_{i}$ like you say - there is a problem with $\binom{n}{k}$. As I understand from your comment : let $a_i = \binom{n}{i}$, then we can't order like you say. – openspace Oct 26 '19 at 14:27
  • @openspace I don't know where you got "$a_i = {n \choose i}$" from, rather than "$a_i = \frac{1}{{n \choose i}}$". In any event, you are right in that the general statement should have "$a_1 > a_2 \ge a_3 \ge \dots \ge a_n$" rather than "$a_1 > a_2 > \dots > a_n$". Now everything should be accurate. – mathworker21 Oct 26 '19 at 15:11
  • @mathworker21 my bad. I guess I understand what do you want to say. – openspace Oct 26 '19 at 15:34
  • @Aqua what actually should we notice from your link? Maybe I don't understand something. – openspace Oct 26 '19 at 15:58
  • @openspace he/she looks advertising his/her problems :) – mathworker21 Oct 26 '19 at 15:59