2つの Turán number

文献によって Turán number の定義が異なるようだったので、それを大きく2つにわけ、その関係を述べる。

定義

定義$n$, $l$, $k$ を正の整数とし $n\geq l\geq k$ とする。$n$ 元集合 $V$ の $k$ 元部分集合からなる族 $F$ は、$V$ の任意の $l$ 元部分集合が $F$ の少なくとも1つの元を包含するとき、turán $(n,l,k)$ system である。

つまり、$F$ が Turán $(n,l,k)$ System であるための必要十分条件は、ある $n$ 元集合 $V$ に対して

  • $\forall e \in F[e\subset V \land |e|=k]$
  • $\forall Y \subset V[|Y|=l\to \exists e\in F[e\subset Y]]$
のすべてを満たすことである。

定義$k$ を正の整数とし $\mathcal{H}$ を $k$-グラフ (辺が $k$ 元集合であるようなハイパーグラフ) とする。$k$-グラフ $\mathcal{G}$ は、$\mathcal{H}$ を部分グラフとして包含しないとき、$\mathcal{H}$-free である。

これら 2 つの対象に対して、2つの非負整数\begin{eqnarray}T(n,l,k)&=&\min\{|F|\mid \text{$F$ は turán $(n,l,k)$ system}\}\\ \text{ex}(n,\mathcal{H})&=&\max\{|F|\mid\text{$(V,F)$ は $n$ 個の頂点を持つ $\mathcal{H}$-free な $k$-グラフ}\} \end{eqnarray}を考えることができ、文献によって前者を Turán number と呼んだり後者を Turán number for $\mathcal{H}$ と呼んだりする。

同じ名前がついているのは、両者に深い関係があるからである。まず上の2つの式の右辺同士を比べると、いずれも $n$-元集合 $V$ に対して $V$ の $k$-元部分集合族 $F\subseteq\binom{V}{k}$ を作っているという点で類似していることがとりあえずわかるだろう。それだけではなく、以下に示すようにこれらの数にはより深い関係がある。

2つの Turán number の関係

命題$n$-元集合 $V$ の $k$-元部分集合族 $F$ が Turán $(n,l,k)$ system であるとき、$k$-グラフ $(V,\binom{V}{k}\setminus F)$ は $\mathcal{K}_k(l)$-free である。

(証明) 以下、$\binom{V}{k}\setminus F$ のことを $F^c$ と表記する。

対偶を示す。$V$ を $n$-元集合とし、$k$-グラフ $(V,F)$ が $\mathcal{K}_k(l)$-free ではないとする。このとき、$(V,F)$ は $\mathcal{K}_k(l)$ を部分グラフとして包含するので、単射な準同型 $f: V(\mathcal{K}_k(l))\to V$ が存在する。このとき、$(V,F)$ の部分グラフ $(\text{im } f, F\cap2^{\text{im } f})$ は完全グラフになるので、$V$ の $l$-元部分集合 $\text{im } f$ の任意の $k$-元部分集合は $F$ に属し、$F^c$ には属さない。したがって $F^c$ は Turán $(n,l,k)$ system ではない。

命題頂点数が $n$ の $k$-グラフ $(V,F)$ が $\mathcal{K}_k(l)$-free であるとき、$F^c = \binom{V}{k}\setminus F$ は Turán $(n,l,k)$ system である。

(証明) 対偶を示す。$V$ を $n$-元集合とし、その $k$-元部分集合族 $F$ が Turán $(n,l,k)$ system ではないとする。このとき、$V$ のある $l$-元部分集合 $Y$ について、その任意の $k$-元部分集合が $F$ に属さず $F^c$ に属する。このとき $(Y, F^c\cap 2^Y)$ は完全グラフであるから、$(V, F^c)$ は完全グラフ $\mathcal{K}_k(l)$ を部分グラフとして包含することになり、したがって $F^c$ は $\mathcal{K}_k(l)$-free でない。

定理\[T(n,l,k) + \text{ex}(n,\mathcal{K}_k(l)) = \binom{ n }{ k }\]

(証明) 命題より\[\text{ex}(n,\mathcal{K}_k(l)) \geq \binom{ n }{ k } - T(n,l,k)\]であり、命題より\[T(n,l,k)\leq \binom{ n }{ k } - \text{ex}(n,\mathcal{K}_k(l)) \]であるので定理が得られる。

この定理から、一方の Turán number が分かれはもう一方の Turán number もわかるので、どちらを Turán number と決めても議論に大きな変更は生まれない。ただし、ハイパーグラフを用いる方は完全グラフ $\mathcal{K}_k(l)$ 以外のグラフの Turán number も考えることができるので、その点で $\text{ex}(n,\mathcal{H})$ の方がより一般化されたものであると言える。

数学  2018/06/15  k.izumi