極値集合論

同義語:extremal set theory

概要

極値集合論(extremal set theory)とは、有限集合の部分集合の族に条件を課したとき、族の大きさの最大値と最大の族の形を問う分野である。代表的な結果は、包含関係のない族の最大の大きさが $\binom{n}{\lfloor n/2\rfloor}$ である Sperner の定理、$n\ge2k$ で交わる $k$ 元部分集合の族の最大の大きさが $\binom{n-1}{k-1}$ である Erdős–Ko–Rado の定理、族の影の大きさの最小値を与える Kruskal–Katona の定理である。方法には二重の数え上げ、圧縮、線形代数、位相幾何がある。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 有限集合, 二項係数, 集合族

極値集合論(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]$ を含む集合だけからなる族を 星 という。

ほかの基本の用語は次のとおりである。

  • 反鎖:相異なるどの 2 元も包含関係にない族(反鎖、Spernerの定理 の Sperner 族)。
  • 影:$k$ 一様な族 $\mathcal F$ の元から 1 点を除いて得られる $(k-1)$ 元集合の全体(Kruskal–Katonaの定理)。
  • 向日葵:相異なるどの 2 元の共通部分も同じ集合になる族(Δ-システム)。

主な問題と結果の一覧

問い代表的な結果入る記事
包含関係のない族はどこまで大きいか最大値は $\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$ に届かない。

$n=4$ の表

$[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の定理 の主張の範囲を示す反例である。

  • $\{12,13,23\}$($n=4$、$k=2$)は大きさが最大の交わる族だが、共通の元がなく星でない。したがって「大きさが最大の交わる族は星である」は $n=2k$ では成り立たない。
  • $\binom{[4]}3$($n=4$、$k=3$)のどの 2 元も 2 点以上を共有するので、これは交わる族である。大きさ $4$ は $\binom{n-1}{k-1}=\binom32=3$ を超える。したがって上界 $\binom{n-1}{k-1}$ は仮定 $n\ge2k$ を外すと成り立たない。

読み進め方

段階読む記事ここで得るもの
1二項係数, 半順序集合, Dilworthの定理数え上げと順序の言葉
2Spernerの定理, Erdős–Ko–Radoの定理平均をとる方法と 2 つの基本定理
3Kruskal–Katonaの定理, Sauer–Shelahの補題圧縮の方法
4組合せ論, Steiner系線形代数の方法(Oddtown の定理、Fisherの不等式)
5Δ-システム, Kneser予想向日葵の評価と位相的な方法
比較極値グラフ理論, Turánの定理グラフの場合の同じ型の問い

入門の短い案内には KT17 §16.2 がある。Katona の円順序の方法の広がりは Fra20 にまとまっている。

未解決問題

  • 和で閉じた族の予想(Frankl の予想):$\mathcal F\subset2^{[n]}$ が和集合で閉じていて $\mathcal F\ne\{\emptyset\}$ なら、$\mathcal F$ の少なくとも半分の元に含まれる $i\in[n]$ があるか。Gilmer は arXiv の報告 Gil22 で、比率 $1/2$ を $0.01$ に下げた形を示した。予想そのものは Gil22(2022 年)の時点で未解決である。
  • Erdős のマッチング予想:$\nu(\mathcal F)$ を $\mathcal F$ の中の互いに交わらない元の最大の個数とする。$n\ge k(r+1)$、$\mathcal F\subset\binom{[n]}k$、$\nu(\mathcal F)\le r$ なら $\lvert\mathcal F\rvert\le\max\bigl\{\binom{k(r+1)-1}k,\binom nk-\binom{n-r}k\bigr\}$ であろうという予想である。$r=1$ は Erdős–Ko–Radoの定理 の上界である。$n>(2r+1)k-r$ では証明されている(Fra20 Theorem 9.2)が、Fra20(2020 年)の時点で全範囲は未解決である。
  • 向日葵予想:$k$ を固定すると、$k$ 個の花びらの向日葵を含まない大きさ $s$ の集合の族の大きさは $C_k^{\,s}$ 以下であろうという予想である。現状は Δ-システム にある。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する