Kneserグラフ

1. $A$ と交わらない $k$ 元集合は、$n-k$ 元集合 $[n]\setminus A$ の $k$ 元部分集合なので $\binom{n-k}k$ 個ある。辺の本数は握手補題による。2. $\binom{n-k}k=0$（$n-k< k$）による。3. $A$ と交わらない $k$ 元集合は補集合 $[2k]\setminus A$ だけである。4. 相異なる 1 元集合は交わらない。$\square$

1. $\sigma$ は全単射なので $\sigma(A)\cap\sigma(B)=\sigma(A\cap B)$ であり、交わらないことが保たれる。順序対については、$A\to A'$、$B\to B'$ を全単射で対応させ、残りの $n-2k$ 個の元どうしも全単射で対応させればよい。頂点の推移性は、$n\ge2k$ なら各頂点が辺をもつのでこれから従い、$n<2k$ でも $A\to A'$ と補集合どうしの全単射で同じように示せる。
2. $\widehat{\sigma\tau}=\hat\sigma\hat\tau$ なので、$\sigma\mapsto\hat\sigma$ は群の準同型である。単射：$\sigma(x)=y\ne x$ となる $x$ があれば、$x\in A$、$y\notin A$ となる $A\in\binom{[n]}k$（$k\le n-1$ なので存在する）について $y\in\sigma(A)$ なので $\hat\sigma(A)\ne A$ である。
   全射：$x\in[n]$ について、$x$ を含む $k$ 元集合の全体を $\mathcal S_x$（星）とする。交わる族は $\mathrm{KG}(n,k)$ の独立集合そのものなので、Erdős–Ko–Radoの定理 の定理「Erdős–Ko–Rado の定理」と定理「等号の場合」（$n>2k$）により、元の個数が最大の独立集合は $n$ 個の星 $\mathcal S_x$ に限る。$x\ne y$ なら $x\in A$、$y\notin A$ となる $A$ があるので、星は互いに異なる。自己同型 $\varphi$ は元の個数が最大の独立集合を同じ性質の集合に写すので、$[n]$ の置換 $\tau$ で $\varphi(\mathcal S_x)=\mathcal S_{\tau(x)}$ となるものが定まる。$A\in\binom{[n]}k$ は $x\in A$ のすべての $\mathcal S_x$ に属するので、$\varphi(A)$ は $x\in A$ のすべての $\mathcal S_{\tau(x)}$ に属し、$\tau(A)\subset\varphi(A)$ である。両辺とも $k$ 元集合なので $\varphi(A)=\tau(A)$、すなわち $\varphi=\hat\tau$ である。$\square$

1. 独立集合は交わる族と同じものなので、Erdős–Ko–Radoの定理 の定理「Erdős–Ko–Rado の定理」と定理「等号の場合」そのものである。2. クリークは互いに交わらない $k$ 元集合の族なので、その個数 $r$ は $rk\le n$ をみたし、$\{1,\dots,k\},\{k+1,\dots,2k\},\dots$ と $\lfloor n/k\rfloor$ 個並べれば等号になる（Kneser予想 の命題「古典的な下界の大きさ」）。3. 同じ色の頂点は独立集合をなすので、$\chi$ 色の塗り分けでは $\binom nk\le\chi\cdot\alpha$ である。$\square$

$\ell$ についての帰納法で、「$\ell$ での 1 $\Rightarrow$ $\ell$ での 2 $\Rightarrow$ $\ell+1$ での 1」を示す。$\ell=0$ での 1 は、長さ $0$ の歩道があることが $A=C$、すなわち $s=k$ と同じであることによる。
長さ $\ell'+1$ の歩道 $A\to C$ があることは、ある $D$ について長さ $\ell'$ の歩道 $A\to D$ があり $D\cap C=\emptyset$ であることと同じである。$D$ は $n-k$ 元集合 $[n]\setminus C$ の $k$ 元部分集合を動く。$[n]\setminus C$ のうち $A$ に属する元は $k-s$ 個、属さない元は $n-2k+s=p+s$ 個である。
$\ell$ での 1 $\Rightarrow$ $\ell$ での 2．$\ell$ での 1 により、条件は $k-\lvert A\cap D\rvert\le\ell p$ となる $D$ があることである。$\lvert A\cap D\rvert$ の最大値は $\min\{k,k-s\}=k-s$（$A\setminus C$ を含む $D$ をとる）なので、条件は $k-(k-s)=s\le\ell p$ である。
$\ell$ での 2 $\Rightarrow$ $\ell+1$ での 1．$\ell$ での 2 により、条件は $\lvert A\cap D\rvert\le\ell p$ となる $D$ があることである。$\lvert A\cap D\rvert$ の最小値は、$D$ に $A$ に属さない元をできるだけ入れて $\max\{0,k-(p+s)\}$ なので、条件は $k-s-p\le\ell p$、すなわち $k-s\le(\ell+1)p$ である。$\square$

距離の式は lem-kg-walk から直ちに従う：長さ $2\ell$ の歩道がある最小の $\ell$ は $\lceil(k-s)/p\rceil$、長さ $2\ell+1$ の歩道がある最小の $\ell$ は $\lceil s/p\rceil$ である。$a:=\lceil(k-s)/p\rceil$、$b:=\lceil s/p\rceil$、$M:=\lceil(k-1)/p\rceil$ とおく。$0\le s\le k-1$ で、どの $s$ もある 2 頂点の共通部分の大きさとして現れる（$2k-s\le n$）。
上界．$a\le b$ なら $\min\{2a,2b+1\}\le2a\le a+b$、$a\ge b+1$ なら $\min\{2a,2b+1\}\le2b+1\le a+b$ なので、距離は $a+b$ 以下である。$s=0$ なら距離は $1\le M+1$ である。$s\ge1$ なら $b=\lfloor(s-1)/p\rfloor+1$ で、$\lceil x\rceil+\lfloor y\rfloor\le\lceil x+y\rceil$ により $a+b\le\lceil(k-s)/p+(s-1)/p\rceil+1=M+1$ である。
下界．$k=1$ なら $M=0$ で、$\mathrm{KG}(n,1)=K_n$（$n\ge3$）の直径は $1$ である。$k\ge2$ なら $M\ge1$ で、距離が $M+1$ 以上の 2 頂点を作る。

始点と終点が同じ歩道を閉じた歩道という。長さ $L$ の奇閉路は長さ $L$ の閉じた歩道である。逆に、奇数の長さの閉じた歩道のうち（始点も動かして）長さが最小のもの $v_0,\dots,v_L$ は閉路である。実際、$0\le i< j\le L$、$(i,j)\ne(0,L)$ で $v_i=v_j$ なら、$v_i,\dots,v_j$ と $v_0,\dots,v_i,v_{j+1},\dots,v_L$ は長さ $j-i$ と $L-(j-i)$ の閉じた歩道で、どちらも $L$ より短く、一方は奇数の長さである。ループがないので $L\ne1$、よって $L\ge3$ である。したがって求める長さは奇数の長さの閉じた歩道の長さの最小値であり、lem-kg-walk の 2 を $C=A$（$s=k$）に当てると、どの始点 $A$ についても $2\lceil k/p\rceil+1$ である。$n\ge3k$ は $p\ge k$ と同じで、このとき長さは $3$ である。$\square$

$[2k+1]$ を $\mathbb Z/(2k+1)\mathbb Z$ と同一視する。安定な $k$ 元集合 $A$ の元を円周の順に並べると、隣り合う元の間隔（$k$ 個）はどれも $2$ 以上で、合計が $2k+1$ なので、ちょうど 1 つが $3$ で残りは $2$ である。間隔 $3$ の直後の元を $a$ とすれば $A=A_a:=\{a,a+2,\dots,a+2(k-1)\}$ であり、逆に各 $A_a$（$a\in\mathbb Z/(2k+1)\mathbb Z$）は安定である。$A_a$ は相異なる $2k+1$ 個の集合である（$a$ は「直前の元が $a-3$」として $A_a$ から決まる）。$2$ の逆数 $h:=k+1$ を掛ける写像 $x\mapsto hx$ は $\mathbb Z/(2k+1)\mathbb Z$ の全単射で、$A_a$ を長さ $k$ の区間 $I_a:=\{ha,ha+1,\dots,ha+k-1\}$ に写す。長さ $k$ の 2 つの区間 $\{c,\dots,c+k-1\}$、$\{c',\dots,c'+k-1\}$ が交わらないことは $c'-c\in\{k,k+1\}$ と同じなので、$A_a$ と $A_b$ が隣接することは $h(b-a)\equiv\pm k$、すなわち $b-a\equiv\pm2k\equiv\mp1$ と同じである。よって $A_a$ を $a$ の順に並べると、隣り合う番号どうしだけが隣接し、$C_{2k+1}$ になる。$\square$