極値集合論(extremal set theory)とは、有限集合の部分集合の族に条件を課したとき、族の大きさの最大値と最大の族の形を問う分野である。代表的な結果は、包含関係のない族の最大の大きさが $\binom{n}{\lfloor n/2\rfloor}$ である Sperner の定理、$n\ge2k$ で交わる $k$ 元部分集合の族の最大の大きさが $\binom{n-1}{k-1}$ である Erdős–Ko–Rado の定理、族の影の大きさの最小値を与える Kruskal–Katona の定理である。方法には二重の数え上げ、圧縮、線形代数、位相幾何がある。
極値集合論(extremal set theory)とは、有限集合の部分集合の族に条件を課したとき、族がどこまで大きくなれるか、最大の族はどんな形かを問う分野である。条件には「どの 2 つも包含関係にない」「どの 2 つも交わる」「決まった形の部分族を含まない」などがある。
たとえば $n$ 元集合の部分集合は全部で $2^n$ 個あるが、どの 2 つも包含関係にない族の大きさの最大値は $\binom n{\lfloor n/2\rfloor}$ である(Spernerの定理)。答えは多くの場合、二項係数の簡単な式で、最大の族は「大きさがちょうど半分」「1 点を含む」のような単純な形をしている。
この記事は分野の地図である。個別の定理の証明はそれぞれの記事にあり、ここでは定義を述べ、問いと結果を表にまとめ、短い完全な証明を 1 つ示す。
$n\ge1$ について $[n]:=\{1,\dots,n\}$ とし、$[n]$ の部分集合の全体を $2^{[n]}$、$k$ 元部分集合の全体を $\binom{[n]}k$ と書く。
$\mathcal F\subset2^{[n]}$ を $[n]$ の 族 という。$\mathcal F\subset\binom{[n]}k$ のとき $k$ 一様 という。族の性質 $P$ を固定し、$P$ をもつ族の大きさの最大値
$$
\max\{\lvert\mathcal F\rvert:\mathcal F\subset2^{[n]},\ \mathcal F\text{ は }P\text{ をもつ}\}
$$
を $n$ の関数として求める問題を 極値問題 という。最大値を与える族を 極値族 という。
ここでの族は冪集合の部分集合で、同じ集合を重複して数えない。添字つきの族との違いは 集合族 にある。$k$ 一様な族は ハイパーグラフ と同じものである。$k=2$ の場合はグラフで、グラフの部分構造を禁止する問題は 極値グラフ理論 が扱う。両方を含む広い分野を極値組合せ論という。
族 $\mathcal F$ の任意の $A,B\in\mathcal F$($A=B$ も含む)について $A\cap B\ne\emptyset$ のとき、$\mathcal F$ は 交わる族 であるという。ある $x\in[n]$ を含む集合だけからなる族を 星 という。
ほかの基本の用語は次のとおりである。
| 問い | 代表的な結果 | 入る記事 |
|---|---|---|
| 包含関係のない族はどこまで大きいか | 最大値は $\binom n{\lfloor n/2\rfloor}$。より強く、反鎖 $\mathcal F$ について $\sum_{A\in\mathcal F}\binom n{\lvert A\rvert}^{-1}\le1$(LYM 不等式) | Spernerの定理, Dilworthの定理 |
| 交わる $k$ 一様な族はどこまで大きいか | $n\ge2k$ なら最大値は $\binom{n-1}{k-1}$ で、星が達成する。$n>2k$ では星に限る | Erdős–Ko–Radoの定理 |
| 星でない交わる族はどこまで大きいか | $n>2k\ge4$ なら $\binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1$ 以下(Hilton–Milner の定理、Fra20 Theorem 5.2) | Erdős–Ko–Radoの定理 |
| $\binom{[n]}k$ は交わる族いくつに分けられるか | 交わる族は Kneserグラフ の独立集合である。$n\ge2k$ のとき、分けるのに必要な個数(彩色数)は $n-2k+2$ である | Kneserグラフ, Kneser予想 |
| 与えられた大きさの族の影はどこまで小さいか | 余辞書式順序の初期区間が最小。$\lvert\mathcal F\rvert=\binom xk$ なら影の大きさは $\binom x{k-1}$ 以上(Lovász の形) | Kruskal–Katonaの定理 |
| 向日葵を含まない族はどこまで大きいか | 大きさ $s$ の集合の族が $s!\,(k-1)^s$ 個より多ければ $k$ 個の花びらの向日葵を含む | Δ-システム |
| 複雑さの低い族はどこまで大きいか | VC 次元が $d$ 以下の族の大きさは $\sum_{i=0}^d\binom ni$ 以下 | Sauer–Shelahの補題, VC次元 |
| 交わりの大きさを指定するとどうなるか | 大きさが奇数で、相異なる 2 元の交わりの大きさが偶数の族は $n$ 個以下(Oddtown の定理)。2-デザイン(ブロックの大きさ $<$ 点の数)のブロックの数は点の数以上(Fisherの不等式) | 組合せ論, Steiner系 |
| 方法 | 考え方 | 使われる場所 |
|---|---|---|
| 重みをつけて 2 通りに数える | 極大鎖や円順序の上で、族の元が占める割合を平均する | Spernerの定理, Erdős–Ko–Radoの定理 |
| 圧縮 | 大きさを保ち、影や打ち砕かれる集合を増やさない操作で、族を標準の形へ移す | Kruskal–Katonaの定理, Sauer–Shelahの補題 |
| 線形代数 | 族の元をベクトルに対応させ、一次独立性と次元で上界を得る | 組合せ論, Steiner系 |
| 代数的位相幾何 | 彩色や被覆の不可能性を球面の写像の性質に帰着する | Kneser予想, Borsuk–Ulamの定理 |
| エントロピー | 無作為に選んだ集合の情報量を比べる | エントロピー, Δ-システム |
一様性の条件を外すと、交わる族の問題は集合と補集合の対に注目するだけで解ける。
$n\ge1$ とする。$\mathcal F\subset2^{[n]}$ が交わる族なら $\lvert\mathcal F\rvert\le2^{n-1}$ である。さらに、極大な交わる族(ほかの部分集合を 1 つでも足すと交わる族でなくなるもの)の大きさはどれもちょうど $2^{n-1}$ である。
$2^{[n]}$ は対 $\{A,[n]\setminus A\}$、$2^{n-1}$ 組に分かれる。$A\cap([n]\setminus A)=\emptyset$ なので、交わる族は各対から高々 1 個しか含まない。したがって $\lvert\mathcal F\rvert\le2^{n-1}$ である。
$\mathcal F$ を極大な交わる族とする。各対から 1 個を含むことを示せば大きさは $2^{n-1}$ である。ある対 $\{A,A'\}$($A':=[n]\setminus A$)の両方が $\mathcal F$ に含まれないとして矛盾を導く。
まず $A=\emptyset$ のとき $A'=[n]$ である。$\mathcal F$ の元は空でないので $\mathcal F\cup\{[n]\}$ は交わる族であり、極大性に反する。$A'=\emptyset$ のときも同じである。
$A,A'$ がともに空でないとする。極大性より $\mathcal F\cup\{A\}$ は交わる族でないので、$A\cap B=\emptyset$ となる $B\in\mathcal F$ がある。同様に $A'\cap C=\emptyset$ となる $C\in\mathcal F$ がある。すると $B\subset A'$、$C\subset A$ なので $B\cap C=\emptyset$ となり、$\mathcal F$ が交わる族であることに反する。$\square$
$\{A:1\in A\}$ は星で、大きさは $2^{n-1}$ である。この命題では「極大なら最大」が成り立つ。反鎖ではこれが成り立たない。Spernerの定理 の例のとおり、$n=4$ の $\{\{1\},\{2,3\},\{2,4\},\{3,4\}\}$ は極大な反鎖だが大きさは $4$ で、最大値 $6$ に届かない。
$[4]$ の族について、条件ごとの最大の大きさは次のとおりである。
| 条件 | 最大の大きさ | 極値族の例 |
|---|---|---|
| 条件なし | $16$ | $2^{[4]}$ |
| 反鎖 | $6=\binom42$ | $\binom{[4]}2$ |
| 交わる族 | $8=2^3$ | $\{A:1\in A\}$ |
| 交わる $2$ 一様な族 | $3=\binom31$ | $\{12,13,14\}$、$\{12,13,23\}$ |
| 交わる $3$ 一様な族 | $4$ | $\binom{[4]}3$ |
交わる一様な族の 2 つの行は、Erdős–Ko–Radoの定理 の主張の範囲を示す反例である。
| 段階 | 読む記事 | ここで得るもの |
|---|---|---|
| 1 | 二項係数, 半順序集合, Dilworthの定理 | 数え上げと順序の言葉 |
| 2 | Spernerの定理, Erdős–Ko–Radoの定理 | 平均をとる方法と 2 つの基本定理 |
| 3 | Kruskal–Katonaの定理, Sauer–Shelahの補題 | 圧縮の方法 |
| 4 | 組合せ論, Steiner系 | 線形代数の方法(Oddtown の定理、Fisherの不等式) |
| 5 | Δ-システム, Kneser予想 | 向日葵の評価と位相的な方法 |
| 比較 | 極値グラフ理論, Turánの定理 | グラフの場合の同じ型の問い |
入門の短い案内には KT17 §16.2 がある。Katona の円順序の方法の広がりは Fra20 にまとまっている。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する