How to visualise Bollobas' 1965 theorem?

Question

Theorem

$[n]=\{1,\ldots,n\}$. Let $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ be such that $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$. Then $$\sum_{i \in I} \frac{1}{{{r_i+s_i}\choose{s_i}}}\le 1.$$

---

Question: I am happy with the proof below of Bollobas' Theorem, but it seems very bashy. Is there a:

• More elegant way to prove the theorem, and, more importantly
• Is there a way to visualise the proof? By this I mean construct a picture on the $n$-cube or similar object that makes the proof somewhat obvious. An example of this is Sperner's Theorem for antichains, visualised by drawing chains on the $n$-cube.

I've already seen one probabilistic proof, which is elegant but I cannot visualise it.

---

Proof

For $n=1$ it is trivial as $I= \lbrace 1 \rbrace$.

We remove an element $x\in [n]$ from the construction to achieve a construction with $n-1$, which we can induct on.

For each $x \in \lbrace 1,...,n \rbrace$ let $I_x= \lbrace i\in I: x \notin R_i \rbrace$, and $S_i^x = S_i \setminus \lbrace x \rbrace$.

$\lbrace (R_i, S_i^x, i \in I_x \rbrace$ we cannot have $R_i \cap S^x_j = \emptyset$, as if $x$ was the only element in common between $R_i$ and $S_j$, that $R_i$ was thrown out as it contained $x$. Anyway, $$\sum_{i \in I_x} \frac{1}{{{r_i+s^x_i}\choose{s^x_i}}}\le 1.$$ Let us vary $x$, and fix $i, R_i, S_i$. Given each $i \in I$, $i \in I_x$ (i.e. $x \notin R_i$) for $n-r_i$ values of $x$. Now, if $i \in I_x$ ($x \notin R_i$), then for $s_i$ values of $x$ we have $s^x_i=s_i-1$ (i.e. $x \in S_i$), and for $n-r_i-s_i$ values of $x$ we have $s_i^x=s_i$. Hence

$$n \ge \sum_{x \in [n]} \sum_{i \in I_x}\frac{1}{{{r_i+s^x_i}\choose{s^x_i}}}= \sum_{i \in I} \frac{n-r_i-s_i}{{{r_i+s_i}\choose{s_i}}}+\frac{s_i}{{{r_i+s_i-1}\choose{s_i-1}}}$$ $$n \ge \sum_{i \in I} \frac{(n-r_i-s_i)(s_i)! (r_i)!}{(s_i+r_i)!}+\frac{s_i (s_i-1)!(r_i)!}{(r_i+s_i-1)!}= n\sum_{i \in I} \frac{1}{{{r_i+s_i}\choose{s_i}}}.$$

Proof 2 (elegant, but still no visualisation)

Randomly order the elements of $[n]$, then $\frac{1}{{{ri+s_i}\choose{s_i}}}$ is the probability that all elements of $R_i$ are greater than those of $S_i$ (written $R_i>S_i$), as only one of the unordered partitions of $[n]$ into $r_i, s_i$ elements satisfies the condition. For all $i$ these events are mutually exclusive. Thus $$P \left( \bigvee_{i \in I} (R_i>S_i) \right)\le 1.$$

---

Answer 1

One perspective on the Bollobas theorem is that it is pretty straightforwardly equivalent to the following theorem about cloud antichains. A cloud antichain in $[n]$ is a collection of intervals $(I_i)_1^m = ([C_i,D_i])_1^m$ such that there do not exist comparable sets coming from different intervals. The theorem states that any cloud antichain in $[n]$ satisfies $$ \sum_1^m \binom{n-d_i+c_i}{c_i}^{-1} \leq 1, $$ where $c_i=|C_i|$, and similar. The proof is that no maximal chain can go through more than one interval, and it is straightforward to see that (assuming I have the statement right) the terms of the sum are the respective probabilities of a uniformly randomly chosen maximal chain going through the $i$-th interval.