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

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

極値集合論とは

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

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

他の例:Erdös-Ko-Radoの定理

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

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

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

  • V={1,2,,n}V=\{1,2,\cdots,n\} の部分集合を「{a,b},{b,c},{c,a}\{a,b\},\{b,c\},\{c,a\} を全て同時に選んではダメ」という制約のもとで最大で何個取ってこれるか考えるとそれは n24\left\lfloor\dfrac{n^2}{4}\right\rfloor 個である,ということです。

  • x\lfloor x \rfloorxx を超えない最大の整数を表します。→ガウス記号の定義と3つの性質

  • テュランの定理の特殊ケースです。

マンテルの定理の証明

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

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

  • nn が奇数の場合
    同様に Kn+12,n12K_{\frac{n+1}{2},\frac{n-1}{2}} を考えればよい。

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

証明

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

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

よって,

uVd(u)2=(u,v)E{d(u)+d(v)}nE\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)d(u) 回足されているので d(u)2d(u)^2 の和と等しい)

また,コーシー・シュワルツの不等式より,

(12++12)(d(1)2++d(n)2)(1^2+\cdots +1^2)(d(1)^2+\cdots +d(n)^2)

(d(1)++d(n))2\,\geq (d(1)+\cdots +d(n))^2

以上から,nnE4E2n\cdot n|E|\geq 4|E|^2

となり示された。

オッドタウンの定理

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

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

  • 各部分集合の要素数は奇数

  • 任意の二つの部分集合の共通の要素数は偶数

久しぶりの数学オリンピックっぽい記事です!