Shannon容量(グラフ)(Shannon capacity of a graph)とは、有限単純グラフ $G$ について、強積のべきの独立数から $\Theta(G)=\sup_k\alpha(G^{\boxtimes k})^{1/k}$ で定める量で、隣接する文字を取り違える通信路で誤りなしに送れる語の増加率を表す。独立数以上でクリーク被覆数以下であり、Lovász の $\vartheta$ と Haemers の階数の不変量がより良い上界を与える。5 頂点の閉路では $\Theta=\sqrt5$ である。$\Theta$ は一般に、強積について乗法的でなく、非交和について加法的でない。
前提知識: グラフ, 独立集合, Kronecker積
グラフの Shannon容量(Shannon capacity of a graph)とは、グラフの頂点を送信する文字とみて、隣接する文字が取り違えられるとするとき、誤りなしで送れる語の数の、語長あたりの増加率である。独立数 $\alpha$ は長さ $1$ の語の数を測り、Shannon 容量はすべての語長の情報をまとめる。
問題の難しさは 5 頂点の閉路にすでに現れる。$\alpha(C_5)=2$ なのに、長さ $2$ の語を使うと 5 個の語を区別でき、容量は $\sqrt5$ になる。この値を確定するには、Lovász の $\vartheta$ という上界が必要である($\vartheta$ の一般の性質は Lovászのθ関数 で扱う)。
| グラフ | $\alpha$ | $\Theta$ | $\vartheta$ | Haemers の上界 |
|---|---|---|---|---|
| $C_5$ | $2$ | $\sqrt5$ | $\sqrt5$ | $3$ |
| Petersen グラフ | $4$ | $4$ | $4$ | |
| 27 本の直線の交点グラフ $\Gamma$ | $6$ | $6$ 以上 $7$ 以下 | $9$ | $7$ 以下 |
| $\Gamma$ の補グラフ | $3$ | $3$ | $3$ |
グラフは有限単純グラフとし、$G$ の頂点集合を $V(G)$、頂点数を $n$ とする。$\bar G$ は補グラフである。
強積 $G\boxtimes H$ は、頂点集合を $V(G)\times V(H)$ とし、異なる 2 点 $(u,v),(u',v')$ を、$u=u'$ または $u\sim u'$ で、かつ $v=v'$ または $v\sim v'$ のとき隣接させたグラフである。$G^{\boxtimes k}$ は $k$ 個の強積である。
$G$ の頂点を文字、辺を「取り違えの可能性」とみると、長さ $k$ の 2 つの語が取り違えられる可能性があるのは、どの位置でも文字が等しいか隣接するときである。したがって $G^{\boxtimes k}$ の独立集合は、誤りなしで区別できる語の集合である。
$$
\Theta(G)=\sup_{k\ge1}\alpha\bigl(G^{\boxtimes k}\bigr)^{1/k}
$$
を $G$ の Shannon容量という。$\log\Theta(G)$ は通信路のゼロ誤り容量である。
独立集合の直積は強積の独立集合なので、$\alpha(G\boxtimes H)\ge\alpha(G)\alpha(H)$ である。よって $\log\alpha(G^{\boxtimes k})$ は優加法的で、Feketeの補題 により上の上限は $k\to\infty$ の極限に等しい。
$\bar\chi(G)=\chi(\bar G)$ をクリーク被覆数、すなわち $V(G)$ を分割するクリークの最小の個数とする。クリークの直積は強積のクリークなので $\bar\chi(G\boxtimes H)\le\bar\chi(G)\bar\chi(H)$ で、$\alpha\le\bar\chi$ と合わせて
$$
\alpha(G)\le\Theta(G)\le\bar\chi(G)
$$
を得る(BH11 p. 43)。
$G$ がパーフェクトグラフなら $\Theta(G)=\alpha(G)$ である。
完全グラフ定理 により $\bar G$ もパーフェクトなので、$\bar\chi(G)=\chi(\bar G)=\omega(\bar G)=\alpha(G)$ である。上の不等式から従う。
たとえば 2 部グラフや偶数の長さの閉路では $\Theta=\alpha$ である。奇数の長さの閉路(長さ $5$ 以上)はパーフェクトでなく、この議論は使えない。
$\mathcal M(G)$ を、$V(G)$ で添字づけた実対称行列 $M$ で、$M_{uu}=1$ と、異なる非隣接な $u,v$ について $M_{uv}=1$ を満たすもの全体とする。隣接する $u,v$ の成分は自由である。
$$
\vartheta(G)=\inf_{M\in\mathcal M(G)}\lambda_{\max}(M)
$$
を $G$ の Lovász 数という。
$\vartheta$ の性質は、ベクトルによる次の言い換えから読みやすくなる。単位ベクトルの族 $(u_v)_{v\in V(G)}$ で、異なる非隣接な $v,w$ について $u_v\perp u_w$ となるものを $G$ の直交表現という。
実数 $t\ge1$ について、次は同値である。
(1)⇒(2):$tI-M$ は半正定値なので、ベクトル $x_v$ のグラム行列である。$|x_v|^2=t-1$、異なる非隣接な $v,w$ で $x_v\cdot x_w=-1$ である。すべての $x_v$ に直交する単位ベクトル $c$ を(次元を増やして)取り、$u_v=(c+x_v)/\sqrt t$ とおくと、$|u_v|^2=1$、非隣接なら $u_v\cdot u_w=0$、$c\cdot u_v=1/\sqrt t$ である。
(2)⇒(1):$z_v=u_v/(c\cdot u_v)-c$ とおく。$|z_v|^2=(c\cdot u_v)^{-2}-1\le t-1$ で、異なる非隣接な $v,w$ で $z_v\cdot z_w=0-1-1+1=-1$ である。$(z_v\cdot z_w)$ に対角行列を足して対角成分をすべて $t-1$ にした半正定値行列を $N$ とすると、$M=tI-N$ は $\mathcal M(G)$ に入り、$\lambda_{\max}(M)\le t$ である。
任意のグラフ $G,H$ について次が成り立つ。
正則グラフの場合. $G$ を $k$ 正則で辺をもつグラフとし、隣接行列 $A$ の最小固有値を $\lambda_{\min}<0$ とする(グラフのスペクトル理論)。
$$
\Theta(G)\le\vartheta(G)\le\frac{-n\lambda_{\min}}{k-\lambda_{\min}}
$$
である。$\operatorname{Aut}(G)$ が辺の集合に推移的に作用するなら、右の不等号は等号である。
$M_c=J+cA$ は $\mathcal M(G)$ に入る。$\mathbf 1$ は固有値 $n+ck$ の固有ベクトルで、$\mathbf 1$ に直交する $A$ の固有ベクトルは固有値 $c\lambda$ をもつ。$c=-n/(k-\lambda_{\min})<0$ とすると、$n+ck$ と $c\lambda_{\min}$ はともに右辺の値で、ほかの $c\lambda$ はそれ以下である。
等号:$M\in\mathcal M(G)$ を $\operatorname{Aut}(G)$ で平均すると、$\lambda_{\max}$ の凸性から $\lambda_{\max}$ は増えず、平均は $\mathcal M(G)$ に入る。辺への推移性から、平均の隣接する成分は一定なので、$J+cA$ の形である。$\lambda_{\max}(J+cA)\ge\max(n+ck,\,c\lambda_{\min})$ で、前者は $c$ について増加、後者は減少するので、右辺は 2 つが等しくなる上の $c$ で最小である。
この上界の主張は BH11 Proposition 3.7.1, 3.7.5(pp. 43–45)にある。
$$
\Theta(C_5)=\sqrt5
$$
である。
下界. 頂点を $\mathbb{Z}/5$ とし、$i\sim i\pm1$ とする。$S=\{(i,2i):i\in\mathbb{Z}/5\}\subset C_5\boxtimes C_5$ が独立集合であることを示す。$(i,2i)$ と $(i+d,2i+2d)$($d\ne0$)を考える。$d=\pm2$ なら第 1 座標が異なり非隣接である。$d=\pm1$ なら第 2 座標の差が $\pm2$ で非隣接である。よって $\alpha(C_5^{\boxtimes2})\ge5$ で、$\Theta(C_5)\ge\sqrt5$ である。
上界. $C_5$ は辺推移的な $2$ 正則グラフで、$\lambda_{\min}=2\cos(4\pi/5)=-\varphi$($\varphi=(1+\sqrt5)/2$)である。prop-scg-regular から
$$
\vartheta(C_5)=\frac{5\varphi}{2+\varphi}=\sqrt5
$$
である。最後の等式は $\sqrt5(2+\varphi)=2\sqrt5+(\sqrt5+5)/2=5(\sqrt5+1)/2=5\varphi$ から従う。thm-scg-theta-basic の (3) から $\Theta(C_5)\le\sqrt5$ である。
長さ $m$ の奇閉路は辺推移的で $\lambda_{\min}=-2\cos(\pi/m)$ なので、
$$
\vartheta(C_m)=\frac{m\cos(\pi/m)}{1+\cos(\pi/m)}
$$
である。$m=7$ では $\vartheta(C_7)\approx3.3177$ である。
Petersenグラフ は $n=10$、$k=3$、$\lambda_{\min}=-2$ で、prop-scg-regular から $\vartheta\le 20/5=4$ である。$\alpha=4$ なので $\Theta=\vartheta=\alpha=4$ である。容量が $\alpha$ に等しいのに、Petersen グラフはパーフェクトでない($C_5$ を誘導部分グラフに含む)。$\bar\chi=5$ なので $\bar\chi$ の上界では足りない。
$C_7$ の容量は 2019 年改訂の文献で未知とされている(Zui18 p. 1)。$C_7^{\boxtimes5}$ に大きさ $367$ の独立集合があり、$\Theta(C_7)\ge367^{1/5}>3.2578$ である(PS18)。
$\vartheta$ は最良の上界ではない。次の階数の上界は、ある種のグラフで $\vartheta$ より強い。
体 $F$ を固定する。$V(G)$ で添字づけた $F$ 上の行列 $B$ で、すべての $u$ について $B_{uu}\ne0$、異なる非隣接な $u,v$ について $B_{uv}=0$ であるものを $G$ に適合する行列という。その階数の最小値を $\mathcal H_F(G)$ と書く。$\mathcal H(G)=\min_F\mathcal H_F(G)$ とおく。
任意の体 $F$ について、$\alpha(G)\le\Theta(G)\le\mathcal H_F(G)\le\bar\chi(G)$ である。
独立集合 $S$ の上で $B$ は対角成分が $0$ でない対角行列なので、$|S|\le\operatorname{rank}B$ である。$B,B'$ が $G,H$ に適合するなら、Kronecker積 $B\otimes B'$ は $G\boxtimes H$ に適合する(異なる非隣接な点はある座標で異なり非隣接で、その座標の成分が $0$ になる)。階数は積になるので、$\alpha(G^{\boxtimes k})\le\mathcal H_F(G)^k$ である。クリーク分割の同じクリークの上で $1$、ほかで $0$ の行列は適合し、階数はクリークの個数である。
$\vartheta$ と $\mathcal H$ の間に大小はない。$\sqrt5\le\mathcal H(C_5)\le\bar\chi(C_5)=3$ で $\mathcal H$ は整数なので $\mathcal H(C_5)=3>\sqrt5=\vartheta(C_5)$ である。逆向きの例が次である。
三次曲面 上の 27 本の直線 $a_i,b_i$($1\le i\le6$)、$c_{ij}$($1\le i< j\le6$)を頂点とし、交わる 2 直線を隣接させたグラフを $\Gamma$ とする。$a_i$ と $b_j$($i\ne j$)、$a_i,b_i$ と $c_{ij}$、$c_{ij}$ と $c_{kl}$($\{i,j\}\cap\{k,l\}=\emptyset$)が隣接し、ほかは隣接しない。これは一般四辺形 $GQ(2,4)$ の共線グラフで、$\Gamma$ の補グラフは Schläfli グラフである(BH11 p. 43)。
$\Gamma$ は $10$ 正則で、スペクトルは $10^1,1^{20},(-5)^6$ である。
$\Theta(G\boxtimes H)\ge\Theta(G)\Theta(H)$ は定義から従う。$\vartheta$ と違い、等号は一般に成り立たない。
$\Theta(\Gamma)\Theta(\bar\Gamma)\le21<27\le\Theta(\Gamma\boxtimes\bar\Gamma)$ である。
ex-scg-gamma から左辺は $21$ 以下である。thm-scg-theta-basic の (4) の証明の対角集合は $\Gamma\boxtimes\bar\Gamma$ の大きさ $27$ の独立集合である。
この現象は「$\vartheta$ では見えない」。$\vartheta(\Gamma)\vartheta(\bar\Gamma)=9\cdot3=27$ で、$\vartheta$ の上界はここでは等号である。
$G+H$ を非交和とする。任意の $G$ について $\Theta(G+\bar G)\ge\sqrt{2n}$ である。$3$ 点部分集合のグラフ $T_m$(頂点は $\{1,\dots,m\}$ の $3$ 点部分集合、ちょうど $1$ 点で交わるとき隣接)は、$m=16$ で
$$
\Theta(T_{16})+\Theta(\overline{T_{16}})\le33<\sqrt{1120}\le\Theta(T_{16}+\overline{T_{16}})
$$
を満たす。
$G$ の頂点 $v$ の、$\bar G$ の中の写しを $v'$ とする。$S=\{(v,v')\}\cup\{(v',v)\}$ は $(G+\bar G)^{\boxtimes2}$ の大きさ $2n$ の独立集合である。実際、$(v,v')$ と $(w,w')$($v\ne w$)は、$G$ で非隣接なら第 1 座標、$\bar G$ で非隣接なら第 2 座標が取り違えられない。$(v,v')$ と $(w',w)$ は第 1 座標が別の連結成分に属する。よって $\Theta(G+\bar G)\ge\sqrt{2n}$ で、$n=\binom{16}3=560$ から右の不等式を得る。
$N$ を、点と $3$ 点部分集合の接続行列($16\times560$)とする。$(N^{\mathsf T}N)_{uv}=|u\cap v|$ である。
$\mathbb{F}_2$ 上で $N^{\mathsf T}N$ の対角成分は $3\equiv1$ で、$T_{16}$ で非隣接な $u\neq v$ は $|u\cap v|\in\{0,2\}$ なので成分は $0$ である。よって $\mathcal H_{\mathbb{F}_2}(T_{16})\le16$ である。
$\mathbb{Q}$ 上で $N^{\mathsf T}N-J$ の対角成分は $2$ で、$\overline{T_{16}}$ で非隣接な $u\ne v$ は $|u\cap v|=1$ なので成分は $0$ である。階数は $17$ 以下である。thm-scg-haemers から $\Theta(T_{16})+\Theta(\overline{T_{16}})\le33$ である。
$\Theta(G+\bar G)\ge\sqrt{2n}$ は Alon の結果であり、これにより $\Theta$ は加法的でない。$\Theta$ の非乗法性は Haemers の結果である(Zui18 Remark 1.2、BH11 p. 43)。$T_m$ と適合行列 $N^{\mathsf T}N$ は BH11 p. 46 の例にある。
情報理論との関係. $\Theta$ は誤りを許さない通信の容量で、誤り確率を $0$ に近づけるだけでよい Shannonの通信路符号化定理 の容量とは別の量である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| prop-scg-perfect のパーフェクト性 | $C_5$ | $\Theta=\sqrt5>2=\alpha$(主張そのものが成り立たない) |
| def-scg-theta の非隣接成分が $1$ | 辺のない $2$ 頂点、$M=I$ | $\lambda_{\max}=1<2=\alpha$(thm-scg-theta-basic の (1) が成り立たない) |
| def-scg-haemers の $B_{uu}\ne0$ | $C_5$、$B=0$ | 階数 $0<2=\alpha$(thm-scg-haemers が成り立たない) |
| def-scg-haemers の非隣接成分が $0$ | 辺のない $2$ 頂点、$B=J$ | 階数 $1<2=\alpha$(thm-scg-haemers が成り立たない) |
| prop-scg-regular の正則性 | $K_{1,3}$($k$ を最大次数 $3$ とする) | 右辺 $=4\sqrt3/(3+\sqrt3)\approx1.46<3=\alpha$(上界が成り立たない) |
| prop-scg-regular の辺への推移性 | $C_5+K_3$ | $\vartheta\le\sqrt5+1\approx3.24$ だが右辺は $8\varphi/(2+\varphi)\approx3.58$(等号が成り立たない) |
6 行目:$C_5$ と $K_3$ の直交表現 $(u_v,c)$、$(u'_w,c')$ を直交する空間に置く。$s=\sqrt5$、$s'=1$ として $c''=\sqrt{s/(s+s')}\,c+\sqrt{s'/(s+s')}\,c'$ とすると、$C_5$ の頂点でも $K_3$ の頂点でも $c''$ との内積の 2 乗は $1/(s+s')$ 以上である。異なる成分の頂点は直交するので直交表現で、$\vartheta(C_5+K_3)\le s+s'$ である。このグラフは $2$ 正則で $n=8$、$\lambda_{\min}=-\varphi$ である。
$\Theta$ の計算が難しい理由. $\vartheta$ と $\mathcal H_F$ はどちらも、$f(G\boxtimes H)\le f(G)f(H)$ を満たす $\alpha$ の上界 $f$ である。このような $f$ について、thm-scg-product の $\Gamma$ では $f(\Gamma)f(\bar\Gamma)\ge\alpha(\Gamma\boxtimes\bar\Gamma)\ge27>21\ge\Theta(\Gamma)\Theta(\bar\Gamma)$ なので、1 つの $f$ で $\Gamma$ と $\bar\Gamma$ の容量を同時に決めることはできない。一方、$\Theta$ は、$1$ 頂点のグラフで $1$ をとり、強積に乗法的、非交和に加法的で、補グラフの準同型が定める順序に単調な関数全体の最小値に等しい(Zui18 Theorem 1.1、p. 2)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する