Bollobásの集合対定理(Bollobás's set-pairs theorem)とは、有限集合の対 $(A_i,B_i)$ が $A_i\cap B_i=\emptyset$ と $A_i\cap B_j\ne\emptyset$($i\ne j$)をみたすとき、$\sum_i\binom{|A_i|+|B_i|}{|A_i|}^{-1}\le1$ が成り立つという極値集合論の不等式である。とくに $|A_i|\le a$、$|B_i|\le b$ なら対の個数は台集合によらず $\binom{a+b}{a}$ 以下で、この上界は交わりを $i<j$ だけに要求する skew 版でも外積代数による証明で成り立つが、重みつきの不等式は skew 版では一般には成り立たない。反鎖についての LYM 不等式は、反鎖の元と補集合の対にこの定理を当てはめたものである。
前提知識: 二項係数, 置換, 外積代数, Vandermondeの行列式
Bollobásの集合対定理(Bollobás's set-pairs theorem)は、有限集合の対 $(A_1,B_1),\dots,(A_m,B_m)$ が「$A_i$ と $B_i$ は交わらないが、$i\ne j$ なら $A_i$ と $B_j$ は交わる」という条件をみたすとき、
$$
\sum_{i=1}^m\binom{|A_i|+|B_i|}{|A_i|}^{-1}\le1
$$
が成り立つという、極値集合論の基本的な不等式である。とくに $|A_i|=a$、$|B_i|=b$ ならば対の個数は $\binom{a+b}{a}$ 以下で、この上界は台集合の大きさによらない。Bollobás が 1965 年に示し、のちに一様な場合が Katona と Jaeger–Payan によって独立に再発見された(帰属は HF24 p. 2 による)。
この記事では、まず無作為な順列を使って重みつきの不等式を証明する。次に、条件を「$i< j$ のときだけ交わる」に弱めた skew 版で、一様な場合の上界 $\binom{a+b}{a}$ がなお成り立つことを外積代数で証明する。重みつきの不等式は skew 版では一般には成り立たないことも例で示す。応用として、反鎖についての LYM 不等式と、横断数について臨界的なハイパーグラフの辺の数の上界を導く。
有限集合の対の列 $\mathcal P=((A_i,B_i))_{i=1}^m$ を考える。
この定義は HF24 p. 1 の Definition 1.1 による。Bollobás 系は skew Bollobás 系である。skew の条件は列の順序に依存し、$i>j$ のとき $A_i\cap B_j$ は空でもよい。Bollobás 系では、$i\ne j$ なら $(A_i,B_i)\ne(A_j,B_j)$ である(等しければ $A_i\cap B_j=A_i\cap B_i=\emptyset$ となる)。skew Bollobás 系でも同じ理由で対は相異なる。
$((A_i,B_i))_{i=1}^m$ を Bollobás 系とし、$a_i:=|A_i|$、$b_i:=|B_i|$ とおく。このとき
$$
\sum_{i=1}^m\binom{a_i+b_i}{a_i}^{-1}\le1
$$
が成り立つ。
この不等式は HF24 p. 2 の Theorem 1.2 にあり、Bollobás(1965)に帰されている。SW21 p. 19 は Bollobás の元の結果がこの重みつきの形(Theorem 4.2)と同値であることを述べ、等号が成り立つのは、ある有限集合 $S$ と整数 $a_0$ について $A_i$ が $S$ の $a_0$ 元部分集合の全体を動き $B_i=S\setminus A_i$ となる場合に限ることも述べている(等号の場合はこの記事では証明しない)。証明は次節の prf-bollobas-main で与える。
$((A_i,B_i))_{i=1}^m$ を Bollobás 系とし、すべての $i$ について $|A_i|\le a$、$|B_i|\le b$ とする。このとき $m\le\binom{a+b}{a}$ である。
$|A_i|=a$、$|B_i|=b$ の場合は HF24 p. 2 の Theorem 1.3、SW21 p. 18 の Theorem 4.1 である。後者は、$m=\binom{a+b}{a}$ となるのは $(a+b)$ 元集合 $S$ があって $A_i$ が $S$ の $a$ 元部分集合の全体を動き $B_i=S\setminus A_i$ となる場合に限ることも述べている。上界が台集合の大きさによらないことがこの定理の特徴である。
組合せ的な証明には Bollobás のものと Katona による数え上げの論法がある(SW21 p. 18)。ここでは、台集合の無作為な並べ方を使う証明を与える。
$m=1$ なら左辺は $\binom{a_1+b_1}{a_1}^{-1}\le1$ である。以下 $m\ge2$ とする。このときすべての $A_i$ と $B_i$ は空でない($A_i=\emptyset$ なら $j\ne i$ について $A_i\cap B_j=\emptyset$ となり条件に反する。$B_i$ も同様)。
$X$ をすべての $A_i,B_i$ を含む有限集合とし、$X$ の元の並べ方($X$ から $\{1,\dots,|X|\}$ への全単射 $\pi$)を一様に無作為に 1 つ選ぶ。$\pi(x)$ を $x$ の位置と呼ぶ。事象 $E_i$ を「$A_i$ のすべての元が、$B_i$ のすべての元より前に並ぶ」とする。
$E_i$ の確率。 $A_i\cup B_i$ の $a_i+b_i$ 個の元の相対的な並び方は、$(a_i+b_i)!$ 通りが等確率で起こる。そのうち $A_i$ の元が先にすべて並ぶのは $a_i!\,b_i!$ 通りなので、
$$
P(E_i)=\frac{a_i!\,b_i!}{(a_i+b_i)!}=\binom{a_i+b_i}{a_i}^{-1}
$$
である。
$E_i$ は互いに排反。 $i\ne j$ について $E_i$ と $E_j$ が同時に起こったとする。$\alpha_i$ を $A_i$ の元の位置の最大値とし、$\alpha_j$ も同様に定める。対称性から $\alpha_i\le\alpha_j$ としてよい。Bollobás 系の条件から $A_i\cap B_j$ の元 $z$ がある。$z\in A_i$ なので $\pi(z)\le\alpha_i$ である。一方 $z\in B_j$ で、$E_j$ により $B_j$ の元は $A_j$ のすべての元より後ろにあるので $\pi(z)>\alpha_j\ge\alpha_i$ である。これは矛盾である。
よって $\sum_iP(E_i)=P(\bigcup_iE_i)\le1$ で、主張を得る。$\square$
対称性で $\alpha_i\le\alpha_j$ としたところで、$A_i\cap B_j\ne\emptyset$ と $A_j\cap B_i\ne\emptyset$ のどちらを使うかが $\alpha$ の大小で決まる。skew の条件では $i< j$ の側しか使えないので、この議論は通らない。実際、重みつきの不等式は skew 版では一般には成り立たない(ex-bollobas-skew-weighted)。
$|A_i|=a_i\le a$、$|B_i|=b_i\le b$ とする。各 $i$ について、ほかのどの集合にも現れない新しい元を $a-a_i$ 個 $A_i$ に、別の新しい元を $b-b_i$ 個 $B_i$ に加えて $A_i'$、$B_i'$ を作る(新しい元は $i$ ごと、$A$ と $B$ ごとに相異なるものを使う)。新しい元は $A_i'\cap B_j'$ に入らないので $A_i'\cap B_i'=\emptyset$ のままで、$i\ne j$ では $A_i'\cap B_j'\supseteq A_i\cap B_j\ne\emptyset$ である。よって $((A_i',B_i'))$ は $|A_i'|=a$、$|B_i'|=b$ の Bollobás 系で、thm-bollobas-main から $m\binom{a+b}{a}^{-1}\le1$ である。$\square$
一様な場合の上界は、交わりの条件を半分にした skew 版でも成り立つ。HF24 p. 2 によれば、Lovász は外積代数(テンソル積)を使って cor-bollobas-uniform の別証明を与え、その証明が skew Bollobás 系にもそのまま通ることが指摘され、Kalai も同じことを示した。SW21 p. 19 は、この緩和を Frankl に帰し、部分空間の形(Theorem 4.3)と集合の形(Corollary 4.4)を述べている。
$((A_i,B_i))_{i=1}^m$ を skew Bollobás 系とし、すべての $i$ について $|A_i|\le a$、$|B_i|\le b$ とする。このとき $m\le\binom{a+b}{a}$ である。
各 $A_i$ に $a$ 次の外積 $w_{A_i}$ を対応させ、それらが 1 次独立であることを示す。1 次独立な元の個数は空間の次元 $\binom{a+b}{a}$ を超えない。外積代数の基本事項は 外積代数 にある:$v\wedge v=0$ と反交換性、$n$ 次元空間の $k$ 次外冪は $\binom nk$ 次元であること、$n$ 個のベクトルの外積は行列式倍の $e_1\wedge\cdots\wedge e_n$ であること、ベクトルが 1 次独立であることとその外積が $0$ でないことの同値性である。証明は prf-bollobas-skew で与える。
$d:=a+b$ とし、相異なる実数 $t$ に対し $v_t:=(1,t,t^2,\dots,t^{d-1})\in\mathbb R^d$ とおく。相異なる実数 $t_1,\dots,t_k$($k\le d$)について $v_{t_1},\dots,v_{t_k}$ は 1 次独立である。
$k=d$ の場合、$v_{t_1},\dots,v_{t_d}$ を列とする行列の行列式は Vandermondeの行列式 $\prod_{i< j}(t_j-t_i)\ne0$ なので 1 次独立である。$k< d$ なら、相異なる実数 $t_{k+1},\dots,t_d$ を追加して $d$ 個にすれば、その一部として 1 次独立である。$\square$
大きさをそろえる。 prf-bollobas-uniform と同じく、各 $A_i$ と $B_i$ に新しい元を足して $|A_i|=a$、$|B_i|=b$ にする。$A_i\cap B_i=\emptyset$ と、$i< j$ での $A_i\cap B_j\ne\emptyset$ は保たれるので、はじめから $|A_i|=a$、$|B_i|=b$ としてよい。
ベクトルを割り当てる。 すべての $A_i,B_i$ を含む有限集合 $X$ の元に相異なる実数 $t_x$ を割り当て、$v_x:=v_{t_x}\in\mathbb R^d$($d=a+b$)とする(lem-bollobas-moment)。$X$ の元に順序を 1 つ決め、$a$ 元集合 $A=\{x_1< \dots< x_a\}$ に対して
$$
w_A:=v_{x_1}\wedge\cdots\wedge v_{x_a}\in{\textstyle\bigwedge^a}\mathbb R^d
$$
とおき、$b$ 元集合 $B$ についても同様に $w_B\in\bigwedge^b\mathbb R^d$ を定める。
交わりと外積。 $|A|=a$、$|B|=b$ のとき、$w_A\wedge w_B\in\bigwedge^d\mathbb R^d$ は $A$ と $B$ の元のベクトルを並べた $d$ 個のベクトルの外積である。$A\cap B\ne\emptyset$ なら同じベクトルが 2 回現れるので $w_A\wedge w_B=0$ である。$A\cap B=\emptyset$ なら $d$ 個の相異なる元のベクトルなので、lem-bollobas-moment により 1 次独立で、$w_A\wedge w_B\ne0$ である。
1 次独立性。 $\sum_{i=1}^mc_iw_{A_i}=0$($c_i\in\mathbb R$)とし、すべての $c_i$ が $0$ であることを示す。そうでないとして、$c_j\ne0$ となる最大の $j$ をとる。右から $w_{B_j}$ との外積をとると
$$
0=\sum_{i=1}^mc_i\,w_{A_i}\wedge w_{B_j}=\sum_{i< j}c_i\,w_{A_i}\wedge w_{B_j}+c_j\,w_{A_j}\wedge w_{B_j}+\sum_{i>j}c_i\,w_{A_i}\wedge w_{B_j}
$$
である。$i< j$ では skew の条件から $A_i\cap B_j\ne\emptyset$ なので $w_{A_i}\wedge w_{B_j}=0$、$i>j$ では $j$ の最大性から $c_i=0$ である。よって $c_j\,w_{A_j}\wedge w_{B_j}=0$ となるが、$A_j\cap B_j=\emptyset$ から $w_{A_j}\wedge w_{B_j}\ne0$ なので $c_j=0$ となり、矛盾する。
次元。 $w_{A_1},\dots,w_{A_m}$ は $\bigwedge^a\mathbb R^d$ の 1 次独立な元で、この空間の次元は $\binom da=\binom{a+b}{a}$ である。よって $m\le\binom{a+b}{a}$ である。$\square$
この証明では $i>j$ のときの $A_i\cap B_j$ を一度も使っていない。使うのは「$c_j\ne0$ となる最大の $j$」という三角形の構造だけである。一方、重みつきの thm-bollobas-main の証明は両方向の交わりを使う。2 つの拡張(重みと skew)は別々の方向に伸びており、集合の大きさに条件を付けなければ同時には成り立たない(ex-bollobas-skew-weighted)。ただし、空でない集合の skew 系で $\lvert A_i\rvert$ が $i$ について減らず $\lvert B_i\rvert$ が増えないなら、重みつきの不等式が成り立つ(SW21 p. 20 の Corollary 4.6。この記事では証明しない)。
$[n]=\{1,\dots,n\}$ のすべての部分集合を、要素の個数が大きい順(同じ個数のものは任意の順)に $A_1,\dots,A_{2^n}$ と並べ、$B_i:=[n]\setminus A_i$ とおく。$i< j$ なら $|A_i|\ge|A_j|$ かつ $A_i\ne A_j$ なので $A_i\not\subseteq A_j$、すなわち $A_i\cap B_j=A_i\setminus A_j\ne\emptyset$ であり、これは skew Bollobás 系である。$|A_i|+|B_i|=n$ なので
$$
\sum_{i=1}^{2^n}\binom{n}{|A_i|}^{-1}=\sum_{k=0}^n\binom nk\cdot\binom nk^{-1}=n+1
$$
となり、$n\ge1$ で $1$ を超える。これは HF24 p. 3 の Example 1 である。同論文の Theorem 1.4(p. 3、証明は p. 6)は、skew Bollobás 系でつねに左辺が $n+1$ 以下であること($n$ は台集合の大きさ)を示している。
一様な場合の skew 版では、上界 $\binom{a+b}{a}$ を達成する系は一つに決まらない。たとえば $B_1$ は $A_1$ と交わらない任意の $b$ 元集合でよい(SW21 p. 19 の脚注)。HF24 pp. 3–4 の Theorem 1.7 は Lovász による部分空間の形で、体 $F$ 上の有限次元空間の $a$ 次元部分空間 $U_i$ と $b$ 次元部分空間 $V_i$ が $U_i\cap V_i=\{0\}$、$i< j$ で $U_i\cap V_j\ne\{0\}$ をみたせば $m\le\binom{a+b}{a}$ であることを述べている。
$F_1,\dots,F_m$ を $[n]$ の相異なる部分集合とし、どの $i\ne j$ についても $F_i\not\subseteq F_j$(反鎖)とする。このとき
$$
\sum_{i=1}^m\binom{n}{|F_i|}^{-1}\le1
$$
である。
$B_i:=[n]\setminus F_i$ とおく。$F_i\cap B_i=\emptyset$ であり、$i\ne j$ では $F_i\cap B_j=F_i\setminus F_j\ne\emptyset$($F_i\not\subseteq F_j$ による)なので、$((F_i,B_i))$ は Bollobás 系である。$|F_i|+|B_i|=n$ なので、thm-bollobas-main から主張を得る。$\square$
この言い換えは HF24 p. 2 にある。LYM 不等式から反鎖の大きさは $\binom n{\lfloor n/2\rfloor}$ 以下であること(Spernerの定理)が従う。同じ記事では LYM 不等式を極大鎖を数える方法で証明している。上の証明の無作為な順列は、極大鎖 $\emptyset\subsetneq\{x_1\}\subsetneq\{x_1,x_2\}\subsetneq\cdots$ を一様に選ぶことと同じであり、事象 $E_i$ は「選んだ鎖が $F_i$ を通る」ことにあたる。
台集合 $V$ の部分集合の族 $\mathcal H$(ハイパーグラフ)について、すべての辺と交わる頂点の集合を 横断、その元の個数の最小値を 横断数 $\tau(\mathcal H)$ という(ハイパーグラフ)。どの辺 $E$ を除いても横断数が小さくなる、すなわち $\tau(\mathcal H\setminus\{E\})<\tau(\mathcal H)$ となるとき、$\mathcal H$ は $\tau$ について臨界的 であるという。
すべての辺が $r$ 元集合であるハイパーグラフ $\mathcal H$ が $\tau(\mathcal H)=t+1$ で、$\tau$ について臨界的ならば、辺の数は $\binom{r+t}{r}$ 以下である。
辺を $E_1,\dots,E_m$ とする。臨界性から、$\tau(\mathcal H\setminus\{E_i\})\le t$ なので、$\mathcal H\setminus\{E_i\}$ には $t$ 元以下の横断 $T_i$ がある。$T_i$ は $E_i$ と交わらない:交わるなら $T_i$ は $\mathcal H$ の横断で、$|T_i|\le t<\tau(\mathcal H)$ に反する。$j\ne i$ では $T_i$ は $\mathcal H\setminus\{E_i\}$ の横断なので $E_j\cap T_i\ne\emptyset$ である。よって $((E_i,T_i))_{i=1}^m$ は $|E_i|=r$、$|T_i|\le t$ の Bollobás 系で、cor-bollobas-uniform から $m\le\binom{r+t}{r}$ である。$\square$
$r=2$(グラフ)の場合、辺の数は $\binom{t+2}{2}$ 以下である。$t+2$ 頂点の完全グラフ $K_{t+2}$ は、頂点被覆の最小の大きさが $t+1$ で、どの辺を除いても $t$ になるので臨界的であり、辺の数はちょうど $\binom{t+2}{2}$ で上界を達成する。
$S$ を $a+b$ 元集合とし、$S$ の $a$ 元部分集合 $A_1,\dots,A_m$($m=\binom{a+b}{a}$)をすべて並べ、$B_i:=S\setminus A_i$ とおく。$A_i\cap B_i=\emptyset$ であり、$i\ne j$ なら $A_i\ne A_j$ で大きさが同じなので $A_i\not\subseteq A_j$、すなわち $A_i\cap B_j\ne\emptyset$ である。よって Bollobás 系で、thm-bollobas-main の左辺はちょうど $1$、cor-bollobas-uniform の上界も達成される。$a=b=1$、$S=\{x,y\}$ なら $(\{x\},\{y\})$、$(\{y\},\{x\})$ の 2 対である。
次の表の各行は、仮定を 1 つだけ外すと結論が成り立たなくなる例である。$m$ は任意の正の整数とする。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $A_i\cap B_i=\emptyset$(def-bollobas-system) | $A_i=\{0,i\}$、$B_i=\{0,-i\}$($i=1,\dots,m$) | どの $i,j$ でも $A_i\cap B_j\ni0$ なので交わりの条件はみたされるが、$\lvert A_i\rvert =\lvert B_i\rvert =2$ で $m$ はいくらでも大きく、$m\le\binom42=6$(cor-bollobas-uniform)が $m=7$ で成り立たない |
| $i\ne j$ で $A_i\cap B_j\ne\emptyset$(def-bollobas-system) | $A_i=\{i\}$、$B_i=\{-i\}$($i=1,\dots,m$) | $A_i\cap B_i=\emptyset$ だが $m$ はいくらでも大きく、$m\le\binom21=2$ が $m=3$ で成り立たない。左辺の和は $m/2$ で $1$ を超える |
| 両方向の交わり(thm-bollobas-main を skew 系に) | ex-bollobas-skew-weighted の系($n=2$) | $(\{1,2\},\emptyset)$、$(\{1\},\{2\})$、$(\{2\},\{1\})$、$(\emptyset,\{1,2\})$ は skew Bollobás 系だが、和は $1+\frac12+\frac12+1=3>1$ |
| 大きさの上限 $\lvert B_i\rvert \le b$(cor-bollobas-uniform) | $A_i=\{i\}$、$B_i=[m]\setminus\{i\}$($i=1,\dots,m$) | $\lvert A_i\rvert =1$ のままで Bollobás 系になり($i\ne j$ なら $i\in B_j$)、対の個数 $m$ は有界でない。thm-bollobas-main の和は $m\cdot\binom{m}{1}^{-1}=1$ で、重みつきの不等式とは矛盾しない |
3 行目では、$i< j$ の 6 通りの組について $A_i\cap B_j\ne\emptyset$ が確かめられる($\{1,2\}$ は $\{2\},\{1\},\{1,2\}$ と交わり、$\{1\}$ は $\{1\},\{1,2\}$ と、$\{2\}$ は $\{1,2\}$ と交わる)。一方 $i>j$ の組では、たとえば $A_4=\emptyset$ はどの $B_j$ とも交わらない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する