5
$\begingroup$

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


$\endgroup$
  • $\begingroup$ I hope that this is relevant on MO. I have posted here earlier. $\endgroup$ – Meow Oct 23 '14 at 23:04
  • 3
    $\begingroup$ Proof 2 in the question seems about as good an explanation as you're likely to find, and one could draw a picture to explain why the events are mutually exclusive (so it's at least kind of visual, in the same way the proof of the LYM inequality is). What more are you hoping for? If you had mentioned only Proof 1 and someone had responded with Proof 2, it would seem like a great answer to me, so I'm not sure what you're looking for. Is there some other sort of visualization you would prefer? $\endgroup$ – Henry Cohn Oct 24 '14 at 0:46
  • $\begingroup$ @HenryCohn I agree with that. A better title would have been 'are there any other or any better ways to visualise Bollobas?'. $\endgroup$ – Meow Oct 24 '14 at 12:43
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.