極値組合せ論における外積代数的手法

次のような極値組合せ論のBollabas*1の結果を紹介します。

定理

$n,p,q$ を $n \geq p+q$ なる自然数とする。 $A_1,\ldots,A_k,B_1,\ldots,B_k \subseteq \{1,\ldots,n\}$ が以下を満たしているとする。

各 $i$ について $|A_i| \leq p, |B_i| \leq q$ .
各 $i$ について $A_i \cap B_i = \emptyset.$
$1 \leq i \lt j \leq k$ ならば、 $A_i \cap B_j \neq \emptyset.$

このとき、 $k \leq \binom{p+q}{p}$ が成り立つ。

ちなみに定理内の上界を等号で達成する例として、 $\{(A,B) : A \subset \{1,\ldots,p+q\}, |A|=p, B=\{1,\ldots,p+q\}-A\}$ があります。

linear algebraic methodの中でも外積代数を用いた非常に綺麗な証明があります。

証明

必要ならば $A_i$ や $B_i$ に適当に元を加えることで、各 $i$ について $|A_i|=p, |B_i|=q$ という仮定の下で定理を示せばよい。

$v_1,\ldots,v_n \in \mathbb{R}^{p+q}$ であって、どの $p+q$ 個も線型独立であるようなものを固定する。 $s_i:=\bigwedge_{e \in A_i} v_e \in \mathbb{R}^{\binom{p+q}{p}}, t_i:=\bigwedge_{a \in B_i}v_e \in \mathbb{R}^{\binom{p+q}{q}}$ とする。すると、仮定より

$i$ について、 $s_i \wedge t_i\neq 0$
$1 \leq i \lt j \leq n$ について、 $s_i \wedge t_j=0$

が成立する。 $s_1, \ldots, s_k$ が線型独立であるならば、 $k \leq \dim \mathbb{R}^{\binom{p+q}{p}}=\binom{p+q}{p}$ が従う。これらが線形独立なことは、 $\sum c_i s_i=0$ なる非ゼロ係数が存在したとすると、最後の非ゼロ成分が $c_j$ であるとすると、 $(\sum c_i s_i)\wedge t_j=c_j s_j \wedge t_j=0$ となり矛盾することから分かる。

コメント

skew-Bollabasの定理とよばれているようです。オリジナルのBollabasの結果は二つ目の条件を「相異なる[\tex: i,j]について」と弱めたもののようです。skew-Bollabasの定理を使う証明はset-pair methodとよばれるようです。
私はMatousekの本
https://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf
で昔ちらっと見かけていたのですが、下の本で、単体的凸多面体の上限定理の証明で使われているのを見つけテンションが上がっていました。次のような議論です。
- 単体複体 $\Delta$ にpartition $\Delta = \coprod [G_i:F_i$ ]が存在するとき、 $B_i:=G_i, A_i:=V(\Delta)-F_i$ は定理の条件を満たす。したがって、skew-Bollabasの定理から、hベクトルの途中までの和を上から評価することができる。実はfベクトルは、hベクトルの途中までの和たちの非負結合で書けるので、fベクトルの上界が得られる。
  www.kyoritsu-pub.co.j

*1:恥ずかしながらmardownでの人名のアクセント記号が分からず、アクセント記号なしで表記します。