|
|
Bollobás 的 Helly 型定理
定理
$[n]=\{1,\ldots,n\}$。设 $\lbrace (R_i, S_i), i \in I \rbrace, R_i, S_i \subset [n]$ 满足 $R_i \cap S_i = \emptyset, R_i \cap S_j \ne \emptyset (i \ne j)$。则 $$\sum_{i \in I} \frac{1}{{{r_i+s_i}\choose{s_i}}}\le 1.$$
____
mathoverflow.net/questions/185240/how-to-visualise-bollobas-1965-theorem
证明
对于 $n=1$，这是显然的，因为 $I= \lbrace 1 \rbrace$。
我们从构造中移除一个元素 $x\in [n]$ 以获得一个 $n-1$ 的构造，可以进行归纳。
对于每个 $x \in \lbrace 1,...,n \rbrace$，设 $I_x= \lbrace i\in I: x \notin R_i \rbrace$，以及 $S_i^x = S_i \setminus \lbrace x \rbrace$。
$\lbrace (R_i, S_i^x, i \in I_x \rbrace$ 我们不能有 $R_i \cap S^x_j = \emptyset$，因为如果 $x$ 是 $R_i$ 和 $S_j$ 之间唯一的公共元素，那么 $R_i$ 会被移除，因为它包含 $x$。无论如何，
$$\sum_{i \in I_x} \frac{1}{{{r_i+s^x_i}\choose{s^x_i}}}\le 1.$$
让我们改变 $x$，并固定 $i, R_i, S_i$。给定每个 $i \in I$，$i \in I_x$（即 $x \notin R_i$）对于 $n-r_i$ 个 $x$ 值。现在，如果 $i \in I_x$（$x \notin R_i$），那么对于 $s_i$ 个 $x$ 值，我们有 $s^x_i=s_i-1$（即 $x \in S_i$），对于 $n-r_i-s_i$ 个 $x$ 值，我们有 $s_i^x=s_i$。因此
$$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}}}.$$
证明 2
随机排列 $[n]$ 的元素，则 $\frac{1}{{{r_i+s_i}\choose{s_i}}}$ 是所有 $R_i$ 元素都大于 $S_i$ 元素的概率（记作 $R_i>S_i$），因为只有一种未排序的 $[n]$ 的划分为 $r_i,s_i$ 个元素的方法满足该条件。对于所有 $i$，这些事件是互斥的。因此
$$P \left( \bigvee_{i \in I} (R_i>S_i) \right)\le 1.$$
|
|
