2015/09/30

極値集合論の美しい2つの定理

分野: グラフ理論  レベル: 数学オリンピック

極値集合論(extremal set theory)の美しい定理を二つ解説します。けっこう難しいですが,数学オリンピックを目指す高校生には理解して欲しい内容です。

極値集合論とは

集合 $V$ の部分集合を,様々な制約のもと最大で(または最小で)何個取ってこれるかを考える分野です。

例えば簡単ですが $V=\{1,2,3\}$ の部分集合で要素数が2のものは最大何個取れるか? という問題です(答えは $\{1,2\},\{1,3\},\{2,3\}$ の3個です)。
他の例:Erdos-Ko-Radoの定理

取ってくる部分集合の要素数が2に固定されている場合,$V$ を頂点集合とするグラフで表現できる(枝 $\{x,y\}$ は要素数2の集合とみなせる)ので極値グラフ理論と言うこともあります。

マンテルの定理(Mantel’s Theorem)

頂点数 $n$ のグラフが三角形を含まないとき,その辺数は $\left\lfloor\dfrac{n^2}{4}\right\rfloor$ 以下である。また,任意の $n$ に対して,辺数が $\left\lfloor\dfrac{n^2}{4}\right\rfloor$ であるような三角形を含まないグラフが存在する。

補足

  • $V=\{1,2,\cdots,n\}$ の部分集合を「 $\{a,b\},\{b,c\},\{c,a\}$ を全て同時に選んではダメ」という制約のもとで最大で何個取ってこれるか考えるとそれは $\left\lfloor\dfrac{n^2}{4}\right\rfloor$ 個である,ということです。
  • $\lfloor x\rfloor$ は $x$ を超えない最大の整数を表します。→ガウス記号の定義と3つの性質
  • テュランの定理の特殊ケースです。

マンテルの定理の証明

まずは主張の後半「任意の $n$ に対して,辺数が $\left\lfloor\dfrac{n^2}{4}\right\rfloor$ であるようなグラフが存在する」を証明します。こちらは簡単です。

証明

$n$ が偶数の場合

頂点を $\dfrac{n}{2}$ ずつに分けてその間を全て辺で結んだグラフ(完全二部グラフ $K_{\frac{n}{2},\frac{n}{2}}$)を考える。このグラフには明らかに三角形がない。そして辺の数は $\dfrac{n^2}{4}$ である。

$n$ が奇数の場合

同様に $K_{\frac{n+1}{2},\frac{n-1}{2}}$ を考えればよい。


続いて前半部分を証明します。

証明

三角形を含まないグラフ $G=(V,E)$ について考える。頂点 $u$ から出ている辺の数を $d(u)$ と書く。

三角形がないという条件から,$(u,v)\in E$ のとき,他の任意の頂点 $w$ に対して$(u,w)\not\in E$ または$(v,w)\not\in E$ である。つまり,$d(u)+d(v)\leq n$

よって,
$\displaystyle\sum_{u\in V}d(u)^2=\sum_{(u,v)\in E}\{d(u)+d(v)\}\leq n|E|$
(真ん中の式では各 $d(u)$ が $d(u)$ 回足されているので $d(u)^2$ の和と等しい)

また,コーシー・シュワルツの不等式より,
$(1^2+\cdots +1^2)(d(1)^2+\cdots +d(n)^2)$ $\,\geq (d(1)+\cdots +d(n))^2$
以上から,$n\cdot n|E|\geq 4|E|^2$
となり題意は示された。

オッドタウンの定理

二つ目です。こちらは証明が難しい(線形代数を用いる)ので定理の主張のみ紹介します。

$V=\{1,2,\cdots,n\}$ の部分集合を以下の二つの条件を満たすように $n+1$ 個以上取ってくることはできない。

  • 各部分集合の要素数は奇数
  • 任意の二つの部分集合の共通の要素数は偶数
久しぶりの数学オリンピックっぽい記事です!
分野: グラフ理論  レベル: 数学オリンピック