|
|
摘自《数学的艺术：孟菲斯的咖啡时间》，第248页
104. 交叉相交族：Bollobás引理
如果有限集对$\left\{\left(A_{i}, B_{i}\right): 1 \leq i \leq m\right\}$是一个交叉相交族，那么
$$
\sum_{i=1}^{m}\left(\begin{array}{c}
\left|A_{i}\right|+\left|B_{i}\right| \\
\left|A_{i}\right|
\end{array}\right)^{-1} \leq 1\tag{36}
$$
第一个证明。 我们可以假设我们的有限集是$[n]$的子集。我们将通过归纳法证明结果。对于$n=0$，断言是显然的，因为只有一对集合$(\emptyset, \emptyset)$。（注意，对于$n=1$有三种可能性。）假设$n \geq 1$且不等式对较小的$n$值成立。设$\mathcal{S}=\left\{\left(A_{i}, B_{i}\right)\right.$ : $1 \leq i \leq m\}$是一个交叉相交族。我们将$\left|A_{i}\right|$和$\left|B_{i}\right|$分别记作$a_{i}$和$b_{i}$。对于$k \in[n]$，设
$$
I_{k}=\left\{i: k \notin A_{i}\right\} \text { 和 } \mathcal{S}_{k}=\left\{\left(A_{i}, B_{i} \backslash\{k\}\right): i \in I_{k}\right\}
$$
由于$\mathcal{S}_{k}$是交叉相交的，根据归纳假设我们有$$\sum_{i \in I_{k}}\left(\begin{array}{c}a_{i}+\left|B_{i} \backslash\{k\}\right| \\ a_{i}\end{array}\right)^{-1} \leq 1$$所以$$\sum_{k=1}^{n} \sum_{i \in I_{k}}\left(\begin{array}{c}a_{i}+\left|B_{i} \backslash\{k\}\right| \\ a_{i}\end{array}\right)^{-1}=\sum_{i=1}^{m} \sum_{k \notin A_{i}}\left(\begin{array}{c}a_{i}+\left|B_{i} \backslash\{k\}\right| \\ a_{i}\end{array}\right)^{-1} \leq n$$因此，
$$
\begin{aligned}
& \sum_{i=1}^{m}\left\{\sum_{k \in B_{i}}\left(\begin{array}{c}
a_{i}+b_{i}-1 \\
a_{i}
\end{array}\right)^{-1}+\sum_{k \notin A_{i} \cup B_{i}}\left(\begin{array}{c}
a_{i}+b_{i} \\
a_{i}
\end{array}\right)^{-1}\right\} \\
=& \sum_{i=1}^{m}\left\{b_{i}\left(\begin{array}{c}
a_{i}+b_{i}-1 \\
a_{i}
\end{array}\right)^{-1}+\left(n-a_{i}-b_{i}\right)\left(\begin{array}{c}
a_{i}+b_{i} \\
a_{i}
\end{array}\right)^{-1}\right\} \leq n .
\end{aligned}\tag{37}
$$
剩下的就是简化上面的求和项，使其显然等价于(36)。为此，注意
$$
\left(\begin{array}{c}
a_{i}+b_{i} \\
a_{i}
\end{array}\right)=\left(\begin{array}{c}
a_{i}+b_{i} \\
b_{i}
\end{array}\right)=\frac{a_{i}+b_{i}}{b_{i}}\left(\begin{array}{c}
a_{i}+b_{i}-1 \\
b_{i}-1
\end{array}\right)=\frac{a_{i}+b_{i}}{b_{i}}\left(\begin{array}{c}
a_{i}+b_{i}-1 \\
a_{i}
\end{array}\right)
$$
因此
$$
b_{i}\left(\begin{array}{c}
a_{i}+b_{i}-1 \\
a_{i}
\end{array}\right)^{-1}=\left(a_{i}+b_{i}\right)\left(\begin{array}{c}
a_{i}+b_{i} \\
a_{i}
\end{array}\right)^{-1}
$$利用这个等式，(37)变为$$\sum_{i=1}^{m} n\left(\begin{array}{c}a_{i}+b_{i} \\ a_{i}\end{array}\right)^{-1} \leq n$$从而证明了(36)。$\square$
第二个证明。 与第一个证明一样，设$\mathcal{S}=\left\{\left(A_{i}, B_{i}\right): 1 \leq i \leq m\right\}$是$[n]$的子集的交叉相交族，且$\left|A_{i}\right|=a_{i}$和$\left|B_{i}\right|=b_{i}$。设$S_{n}$为$[n]$的所有$n!$个排列的对称群，并通过使其元素等概率来将$S_{n}$变为一个概率空间。对于$1 \leq i \leq m$，设$E_{i}$为$A_{i}$的元素在$B_{i}$的元素之前的事件：
$$
E_{i}=\left\{\pi \in S_{n}: \pi(a)<\pi(b) \text { 如果 } a \in A_{i} \text { 且 } b \in B_{i}\right\}
$$
那么
$$
\mathbb{P}\left(E_{i}\right)=\left(\begin{array}{c}
a_{i}+b_{i} \\
a_{i}
\end{array}\right)^{-1}
$$
因为$\pi \in E_{i}$当且仅当$\pi$在$A_{i} \cup B_{i}$上的限制（这是一个有$a_{i}+b_{i}$个元素的集合）将$A_{i}$映射到$\pi\left(A_{i} \cup B_{i}\right)$的前$a_{i}$个元素中。
我们声称事件$E_{1}, \ldots, E_{m}$是两两不相交的。因为，如果$\pi \in E_{i}$，即集合$\pi\left(A_{i}\right)$在$\pi\left(B_{i}\right)$之前，那么，对于$j \neq i$，集合$\pi\left(A_{j}\right)$在$\pi\left(B_{i}\right)$中有一个元素，而集合$\pi\left(B_{j}\right)$在$\pi\left(A_{j}\right)$中有一个元素。因此，$\pi\left(A_{j}\right)$不在$\pi\left(B_{j}\right)$之前，所以$\pi \notin E_{j}$。
最后，由于事件$E_{1}, \ldots, E_{m}$是两两不相交的，
$$
\sum_{i=1}^{m}\left(\begin{array}{c}
a_{i}+b_{i} \\
a_{i}
\end{array}\right)^{-1}=\sum_{i=1}^{m} \mathbb{P}\left(E_{i}\right)=\mathbb{P}\left(\bigcup_{i=1}^{m} E_{i}\right) \leq 1
$$
完成了我们的证明。$\square$
link.springer.com/article/10.1007/s00373-004-0598-4 |
|
