Shannon容量(グラフ)

同義語:Shannon capacity of a graphグラフのShannon容量

概要

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$ は一般に、強積について乗法的でなく、非交和について加法的でない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 独立集合, 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}$ の独立集合は、誤りなしで区別できる語の集合である。

グラフの Shannon 容量

$$ \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$ 以上)はパーフェクトでなく、この議論は使えない。

Lovász の上界

$\mathcal M(G)$ を、$V(G)$ で添字づけた実対称行列 $M$ で、$M_{uu}=1$ と、異なる非隣接な $u,v$ について $M_{uv}=1$ を満たすもの全体とする。隣接する $u,v$ の成分は自由である。

Lovász の $\vartheta$

$$ \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. $\lambda_{\max}(M)\le t$ となる $M\in\mathcal M(G)$ がある。
  2. $G$ の直交表現 $(u_v)$ と単位ベクトル $c$ で、すべての $v$ について $(c\cdot u_v)^2\ge1/t$ となるものがある。

(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$ である。

$\vartheta$ の基本不等式

任意のグラフ $G,H$ について次が成り立つ。

  1. $\alpha(G)\le\vartheta(G)\le\bar\chi(G)$
  2. $\vartheta(G\boxtimes H)\le\vartheta(G)\vartheta(H)$
  3. $\Theta(G)\le\vartheta(G)$
  4. $\vartheta(G)\vartheta(\bar G)\ge n$
テンソル積で直交表現を作る
  1. $S$ を独立集合、$M\in\mathcal M(G)$ とする。$M$ の $S$ の主小行列は全成分が $1$ の行列で、最大固有値は $|S|$ である。固有値の絡み合いから $\lambda_{\max}(M)\ge|S|$ である。
    $V(G)$ を $k$ 個のクリーク $C_1,\dots,C_k$ に分割し、正規直交系 $e_1,\dots,e_k$ を取る。$v\in C_i$ に $u_v=e_i$ を当てると直交表現である(非隣接な 2 点は別のクリークに入る)。$c=k^{-1/2}\sum_ie_i$ について $(c\cdot u_v)^2=1/k$ なので、prop-scg-representation から $\vartheta(G)\le k$ である。
  2. $t>\vartheta(G)$、$t'>\vartheta(H)$ を取り、prop-scg-representation の $(u_v,c)$、$(u'_w,c')$ を取る。$(v,w)\mapsto u_v\otimes u'_w$ を考える。$(v,w),(v_1,w_1)$ が $G\boxtimes H$ で異なる非隣接な点なら、ある座標で 2 点は異なり非隣接である。その座標で内積が $0$ なので、$(u_v\cdot u_{v_1})(u'_w\cdot u'_{w_1})=0$ である。よって $G\boxtimes H$ の直交表現である。$\bigl((c\otimes c')\cdot(u_v\otimes u'_w)\bigr)^2\ge1/(tt')$ なので、$\vartheta(G\boxtimes H)\le tt'$ である。
  3. (1)(2) から $\alpha(G^{\boxtimes k})\le\vartheta(G^{\boxtimes k})\le\vartheta(G)^k$ である。
  4. 対角集合 $\{(v,v)\}$ は $G\boxtimes\bar G$ の独立集合である。実際、$v\ne w$ なら $v,w$ は $G$ と $\bar G$ のどちらかで非隣接である。(1)(2) から $n\le\vartheta(G\boxtimes\bar G)\le\vartheta(G)\vartheta(\bar G)$ である。
  1. で等号が成り立つこと、頂点推移的なグラフで (4) の等号が成り立つことは Lovász の結果である(BH11 pp. 44–45 に主張がある。この記事では証明しない)。
    $\vartheta$ は 半正定値計画 で表される。$\vartheta(G)=\sup\operatorname{tr}NJ$ で、$N$ は跡が $1$ の半正定値行列で隣接する $u,v$ について $N_{uv}=0$ を満たすものを動き、$J$ は全成分 $1$ の行列である(BH11 p. 45)。$\alpha$ と $\bar\chi$ の計算は NP 完全だが、$\vartheta$ は任意の精度で多項式時間で計算できる(BH11 p. 44)。thm-scg-theta-basic の (1) を補グラフに当てた $\omega(G)\le\vartheta(\bar G)\le\chi(G)$ が、いわゆるサンドイッチ定理である(Knu94 p. 2。$\vartheta$ の規約はこの記事と同じで、同 (4.9)、p. 7)。

正則グラフの場合. $G$ を $k$ 正則で辺をもつグラフとし、隣接行列 $A$ の最小固有値を $\lambda_{\min}<0$ とする(グラフのスペクトル理論)。

固有値による上界

$$ \Theta(G)\le\vartheta(G)\le\frac{-n\lambda_{\min}}{k-\lambda_{\min}} $$
である。$\operatorname{Aut}(G)$ が辺の集合に推移的に作用するなら、右の不等号は等号である。

行列を 1 径数に絞る

$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)にある。

五角形の容量

$C_5$ の Shannon 容量

$$ \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$ である。

奇閉路と 10 頂点の例

長さ $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)。

Haemers の上界

$\vartheta$ は最良の上界ではない。次の階数の上界は、ある種のグラフで $\vartheta$ より強い。

Haemers の不変量

体 $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)$ とおく。

Haemers の上界

任意の体 $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 本の直線の交点グラフ

三次曲面 上の 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$ である。

  • $A-I$ は $\Gamma$ に適合し、階数は $27-20=7$ なので、$\Theta(\Gamma)\le\mathcal H_{\mathbb{Q}}(\Gamma)\le7$ である。
  • $\alpha(\Gamma)=6$ である($a_1,\dots,a_6$ が大きさ $6$ の独立集合で、値は BH11 p. 43)。prop-scg-regular の右辺は $27\cdot5/15=9$ なので $\vartheta(\Gamma)\le9$ である。次の項の $\vartheta(\bar\Gamma)\le3$ と thm-scg-theta-basic の (4) から $\vartheta(\Gamma)\ge27/3=9$ なので、$\vartheta(\Gamma)=9$ である(BH11 p. 46 の値と一致する)。したがって $\mathcal H(\Gamma)<\vartheta(\Gamma)$ である。
  • $\bar\Gamma$ は $16$ 正則で最小固有値 $-2$ なので、$\vartheta(\bar\Gamma)\le27\cdot2/18=3$ である。同一平面上の 3 直線 $a_1,b_2,c_{12}$ から $\alpha(\bar\Gamma)\ge3$ なので、$\Theta(\bar\Gamma)=3$ である。

積と和で成り立たないこと

$\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}}) $$
を満たす。

2 つの体で適合する行列を作る

$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アソシエイト)の紹介料で運営されています。 支援について / 寄付する