Lovászのθ関数(Lovász theta function)とは、有限単純グラフ $G$ に、対角成分と隣接しない 2 頂点の成分を 1 と定めた対称行列の最大固有値の最小値 $\vartheta(G)$ を対応させる関数である。同じ値は、半正定値行列についての半正定値計画の最大値や、直交表現による 2 通りの最適化の値としても表される。独立数とクリーク被覆数の間にはさまれ、強積について乗法的で、補グラフとの積は頂点数以上、頂点推移的なら頂点数に等しい。パーフェクトグラフでは独立数に一致し、Shannon 容量の上界を与える。
Lovászのθ関数(Lovász theta function)とは、有限単純グラフ $G$ に実数 $\vartheta(G)$ を対応させる関数で、成分の一部を指定した対称行列の最大固有値の最小値として定まる。$\vartheta(G)$ は独立数 $\alpha(G)$ とクリーク被覆数 $\bar\chi(G)=\chi(\bar G)$ の間にはさまれ、どちらも計算が難しい 2 つの整数の間に、半正定値計画 で計算できる実数を差し込む。L. Lovász は 1979 年にこの量を導入し、5 頂点の閉路のグラフの Shannon 容量が $\sqrt5$ であることを示した(Lov79)。
$\vartheta$ の値打ちは、同じ数がまったく違う 4 つの最適化問題の値として現れることにある。最小化の問題からは上界が、最大化の問題からは下界が得られ、両者が一致するので、どちらの側でも証拠を示せる。この記事では 4 つの表示の一致を証明し、そこから強積についての乗法性と、頂点推移的なグラフでの等式 $\vartheta(G)\vartheta(\bar G)=n$ を導く。
| 結果 | 内容 | この記事での扱い |
|---|---|---|
| thm-lt-main | 4 つの表示の一致(強双対性) | 証明する |
| cor-lt-sandwich | $\alpha(G)\le\vartheta(G)\le\bar\chi(G)$ | 証明する |
| thm-lt-product | $\vartheta(G\boxtimes H)=\vartheta(G)\vartheta(H)$ | 証明する |
| thm-lt-transitive | $\vartheta(G)\vartheta(\bar G)\ge n$、頂点推移的なら等号 | 証明する |
| prop-lt-perfect | パーフェクトグラフで $\vartheta=\alpha$ | 証明する |
グラフ $G$ は頂点数 $n\ge1$ の有限単純グラフとし、頂点集合を $V$ とする。$u\sim v$ で隣接を表す。$J$ は全成分が $1$ の $n$ 次行列、$\mathbf 1$ は全成分が $1$ のベクトルである。実対称行列 $A$ の最大固有値を $\lambda_{\max}(A)$ と書き、半正定値であることを $A\succeq0$ と書く。強積 $G\boxtimes H$ とクリーク被覆数 $\bar\chi$ は Shannon容量(グラフ) の定義に従う。
$V$ で添字づけた実対称行列 $M$ で、すべての $u$ について $M_{uu}=1$、隣接しない相異なる $u,v$ について $M_{uv}=1$ をみたすもの全体を $\mathcal M(G)$ とする(隣接する $u,v$ の成分は自由である)。
$$
\vartheta(G)=\min_{M\in\mathcal M(G)}\lambda_{\max}(M)
$$
を $G$ の Lovász の θ 関数、または Lovász 数 という。
最小値は存在する。$x=(e_u\pm e_v)/\sqrt2$ について $x^{\mathsf T}Mx=1\pm M_{uv}\le\lambda_{\max}(M)$ なので、$\lambda_{\max}(M)\le t$ となる $M$ の成分は $|M_{uv}|\le t-1$ で抑えられ、その全体はコンパクトだからである。$J\in\mathcal M(G)$ なので $\vartheta(G)\le n$ である。
このほかの表示に使う語を定める。単位ベクトルの族 $(u_v)_{v\in V}$ で、隣接しない相異なる $v,w$ について $u_v\perp u_w$ となるものを $G$ の 直交表現 という(Shannon容量(グラフ) と同じ)。$\bar G$ の直交表現は、$G$ で隣接する 2 頂点を直交させる単位ベクトルの族である。
$A$ を実対称行列とし、$\mathcal K=\{B\succeq0\mid\operatorname{tr}B=1\}$ とおく。このとき
$$
\lambda_{\max}(A)=\max_{B\in\mathcal K}\operatorname{tr}(AB)
$$
である。とくに $A\succeq0$、$B\succeq0$ なら $\operatorname{tr}(AB)\ge0$ である。
$B\in\mathcal K$ を スペクトル定理 で $B=\sum_i\mu_ix_ix_i^{\mathsf T}$($\mu_i\ge0$、$\sum_i\mu_i=1$、$x_i$ は単位ベクトル)と書くと、$\operatorname{tr}(AB)=\sum_i\mu_i\,x_i^{\mathsf T}Ax_i\le\lambda_{\max}(A)$ である。$x$ を $\lambda_{\max}(A)$ の単位固有ベクトルとして $B=xx^{\mathsf T}$ をとると等号が成り立つ。後半は、同じ展開で $x_i^{\mathsf T}Ax_i\ge0$ となることによる。$\square$
次の 4 つの数はすべて $\vartheta(G)$ に等しい。
$\vartheta_2$ は 半正定値計画 の形の最大化問題で、$\vartheta_1$ はその双対問題である。$\operatorname{tr}(JB)=\sum_{u,v}B_{uv}$ に注意する。
1.弱双対性 $\vartheta_2\le\vartheta_1$. $M\in\mathcal M(G)$ と 2 の条件をみたす $B$ をとる。$M-J$ の成分は隣接する $u,v$ の位置にしかなく、そこで $B_{uv}=0$ なので $\operatorname{tr}((M-J)B)=0$ である。lem-lt-trace から
$$
\operatorname{tr}(JB)=\operatorname{tr}(MB)\le\lambda_{\max}(M)\operatorname{tr}B=\lambda_{\max}(M)
$$
である。2 の条件をみたす $B$ の全体はコンパクトで空でない($B=\frac1nI$)ので、最大値は達成される。
2.強双対性 $\vartheta_1\le\vartheta_2$. 辺の集合を $E$ とし、写像 $\Phi:B\mapsto\bigl(\operatorname{tr}(JB),(B_{uv})_{uv\in E}\bigr)\in\mathbb R\times\mathbb R^E$ を考える。$\mathcal K$ はコンパクトな凸集合なので $\Phi(\mathcal K)$ もそうであり、
$$
\mathcal S=\Phi(\mathcal K)+\bigl((-\infty,0]\times\{0\}\bigr)
$$
は閉凸集合である。$\vartheta_2< t$ となる $t$ をとると、$(t,0)\notin\mathcal S$ である($\mathcal S$ に入れば $B_{uv}=0$($uv\in E$)かつ $\operatorname{tr}(JB)\ge t$ となる $B\in\mathcal K$ がある)。閉凸集合と点の分離(Hahn–Banachの定理 の有限次元の場合)により、$(\lambda,y)\in\mathbb R\times\mathbb R^E$ と実数 $\gamma$ で、すべての $(s,b)\in\mathcal S$ について
$$
\lambda s+\sum_{uv\in E}y_{uv}b_{uv}\le\gamma< \lambda t
$$
となるものがある。$s$ はいくらでも小さくとれるので $\lambda\ge0$ である。$\lambda=0$ なら $B=\frac1nI$($b=0$)で $0\le\gamma<0$ となり矛盾するので、$\lambda>0$ で、$\lambda=1$ としてよい。$X$ を、$uv\in E$ の位置に $X_{uv}=X_{vu}=\frac12y_{uv}$、ほかは $0$ の対称行列とすると、$M=J+X\in\mathcal M(G)$ で、すべての $B\in\mathcal K$ について $\operatorname{tr}(MB)=\operatorname{tr}(JB)+\sum_{uv\in E}y_{uv}B_{uv}\le\gamma$ である。lem-lt-trace から $\lambda_{\max}(M)\le\gamma< t$、よって $\vartheta_1< t$ である。$t>\vartheta_2$ は任意なので $\vartheta_1\le\vartheta_2$ である。
3.$\vartheta_4=\vartheta_2$. $(b_v)$ を $\bar G$ の直交表現、$d$ を単位ベクトルとし、$S=\sum_v(d\cdot b_v)^2$ とおく。$S>0$ の場合を考えればよい。$w_v=(d\cdot b_v)b_v$ の Gram行列 を $S$ で割った $B_{uv}=w_u\cdot w_v/S$ は半正定値で、$\operatorname{tr}B=1$、$u\sim v$ なら $b_u\perp b_v$ なので $B_{uv}=0$ である。さらに $\sum_vw_v$ と $d$ の内積は $S$ なので、Cauchy–Schwarzの不等式 から
$$
\operatorname{tr}(JB)=\frac{\bigl|\sum_vw_v\bigr|^2}{S}\ge\frac{S^2}{S}=S
$$
である。よって $\vartheta_4\le\vartheta_2$ である。
逆に、2 の最大値を達成する $B$ をとり、$B_{uv}=w_u\cdot w_v$ と分解する。$\vartheta_2=\bigl|\sum_vw_v\bigr|^2>0$($\vartheta_2\ge\operatorname{tr}(J\cdot\frac1nI)=1$)なので $d=\sum_vw_v/\bigl|\sum_vw_v\bigr|$ とおける。$w_v\ne0$ なら $b_v=w_v/|w_v|$、$w_v=0$ なら $b_v$ をほかのすべてのベクトルと直交する新しい単位ベクトル(互いにも直交させる)とする。$u\sim v$ なら $w_u\cdot w_v=0$ なので $(b_v)$ は $\bar G$ の直交表現である。Cauchy–Schwarz の不等式から
$$
\sum_v(d\cdot b_v)^2\ge\frac{\bigl(\sum_v|w_v|\,(d\cdot b_v)\bigr)^2}{\sum_v|w_v|^2}=\frac{\bigl(d\cdot\sum_vw_v\bigr)^2}{\operatorname{tr}B}=\Bigl|\sum_vw_v\Bigr|^2=\vartheta_2
$$
である。よって $\vartheta_4\ge\vartheta_2$ で、上限はこの $(b_v),d$ で達成される。
4.$\vartheta_3=\vartheta_1$. Shannon容量(グラフ) の命題「行列と直交表現」は、実数 $t\ge1$ について、$\lambda_{\max}(M)\le t$ となる $M\in\mathcal M(G)$ があることと、直交表現 $(u_v)$ と単位ベクトル $c$ で $(c\cdot u_v)^2\ge1/t$ となるものがあることが同値であることを示している。$\vartheta_1\ge1$($\operatorname{tr}M=n$ なので $\lambda_{\max}(M)\ge1$)だから、これは $\vartheta_3=\vartheta_1$ を意味する。$\square$
この 4 つは Knu94 の $\vartheta_2,\vartheta_3,\vartheta_1,\vartheta_4$(重みがすべて $1$ の場合)に当たり、一致は同 §12 の定理(pp. 14–15)である。そこでは強双対性を、錐についての初等的な事実(§8–§9)から導いている。
最小化の側(1 と 3)では、行列 $M$ や直交表現を 1 つ示せば上界 $\vartheta(G)\le\lambda_{\max}(M)$ が得られ、最大化の側(2 と 4)では、行列 $B$ やベクトルの族を 1 つ示せば下界が得られる。以下の証明はすべてこの使い分けでできている。
下界. $S$ を大きさ $s$ の 独立集合 とし、$\mathbf 1_S$ を $S$ の指示ベクトルとして $B=\frac1s\mathbf 1_S\mathbf 1_S^{\mathsf T}$ とおく。$B\succeq0$、$\operatorname{tr}B=1$ で、$B_{uv}\ne0$ となるのは $u,v\in S$ のときだけであり、そのとき $u,v$ は隣接しない。よって $B$ は thm-lt-main の 2 の条件をみたし、$\operatorname{tr}(JB)=s^2/s=s$ なので $\vartheta(G)\ge s$ である。
上界. $V$ を $k$ 個のクリーク $Q_1,\dots,Q_k$ に分割し、$J_{Q_i}=\mathbf 1_{Q_i}\mathbf 1_{Q_i}^{\mathsf T}$ として
$$
M=J-k\sum_{i=1}^kJ_{Q_i}+kI
$$
とおく。対角成分は $1-k+k=1$ である。隣接しない相異なる $u,v$ は別々のクリークに入るので $M_{uv}=1$ であり、$M\in\mathcal M(G)$ である。$x\in\mathbb R^V$ について、$\sigma_i=\sum_{v\in Q_i}x_v$ とおくと Cauchy–Schwarz の不等式から
$$
x^{\mathsf T}\Bigl(k\sum_iJ_{Q_i}-J\Bigr)x=k\sum_{i=1}^k\sigma_i^2-\Bigl(\sum_{i=1}^k\sigma_i\Bigr)^2\ge0
$$
なので $kI-M\succeq0$、つまり $\lambda_{\max}(M)\le k$ である。よって $\vartheta(G)\le k$ である。$\square$
$\omega(G)\le\vartheta(\bar G)\le\chi(G)$ の形が、Knu94 の題にある「サンドイッチ定理」である(p. 2 の (∗)、(4.9) p. 7)。$\alpha(G)\ge k$、$\omega(G)\ge k$、$\chi(G)\le k$ を判定する問題はどれも NP完全問題 であるが、$\vartheta$ は 半正定値計画 の値なので、楕円体法によって任意の精度で多項式時間で計算できる(Grötschel–Lovász–Schrijver、Knu94 p. 2・p. 45)。
強積 $G\boxtimes H$ は、頂点集合 $V(G)\times V(H)$ の上で、相異なる $(g,h),(g',h')$ を、各成分が等しいか隣接しているときに隣接させたグラフである。したがって、相異なる 2 頂点が強積で隣接しないのは、ある成分が相異なりかつ隣接しないときである。
有限単純グラフ $G,H$ について $\vartheta(G\boxtimes H)=\vartheta(G)\vartheta(H)$ である。
$\le$. $\varepsilon>0$ とし、thm-lt-main の 3 で、$G$ の直交表現 $(u_g)$ と単位ベクトル $c$ を $(c\cdot u_g)^{-2}\le\vartheta(G)+\varepsilon$ となるように、$H$ についても $(u'_h)$、$c'$ を同様にとる。$w_{(g,h)}=u_g\otimes u'_h$ は単位ベクトルで、$(g,h),(g',h')$ が強積で隣接しなければ、たとえば $g\ne g'$ かつ $g,g'$ が隣接しないので $w_{(g,h)}\cdot w_{(g',h')}=(u_g\cdot u_{g'})(u'_h\cdot u'_{h'})=0$ である。よって $(w_{(g,h)})$ は $G\boxtimes H$ の直交表現で、$c\otimes c'$ について $\bigl((c\otimes c')\cdot w_{(g,h)}\bigr)^{-2}=(c\cdot u_g)^{-2}(c'\cdot u'_h)^{-2}\le(\vartheta(G)+\varepsilon)(\vartheta(H)+\varepsilon)$ である。$\varepsilon\to0$ として $\vartheta(G\boxtimes H)\le\vartheta(G)\vartheta(H)$ である。
$\ge$. thm-lt-main の 2 の最大値を達成する $B_G$、$B_H$ をとり、Kronecker積 $B=B_G\otimes B_H$ を考える。$B$ は半正定値で $\operatorname{tr}B=\operatorname{tr}B_G\operatorname{tr}B_H=1$ である。$(g,h),(g',h')$ が強積で隣接するとき、$g\ne g'$ なら $g,g'$ は隣接するので $(B_G)_{gg'}=0$、$g=g'$ なら $h,h'$ が隣接するので $(B_H)_{hh'}=0$ で、どちらでも $B$ の成分は $0$ である。$J_{G\boxtimes H}=J_G\otimes J_H$ なので
$$
\operatorname{tr}(J_{G\boxtimes H}B)=\operatorname{tr}(J_GB_G)\operatorname{tr}(J_HB_H)=\vartheta(G)\vartheta(H)
$$
であり、$\vartheta(G\boxtimes H)\ge\vartheta(G)\vartheta(H)$ である。$\square$
上界の半分は Shannon容量(グラフ) の基本不等式の (2) と同じ議論で、そこから Shannon 容量について $\Theta(G)\le\vartheta(G)$ が出る。等式は Knu94 の (20.5)(p. 22)である。
頂点数 $n$ のグラフ $G$ について $\vartheta(G)\vartheta(\bar G)\ge n$ である。グラフの自己同型 群が頂点集合に推移的に作用するとき(頂点推移的なとき)は $\vartheta(G)\vartheta(\bar G)=n$ である。
$\ge$. $\varepsilon>0$ とし、$G$ の直交表現 $(u_v)$ と単位ベクトル $c$ を $(c\cdot u_v)^2\ge1/(\vartheta(G)+\varepsilon)$ となるようにとる(thm-lt-main の 3)。$\bar G$ の補グラフは $G$ なので、$(u_v)$ は thm-lt-main の 4 を $\bar G$ に当てはめたときの条件をみたし、
$$
\vartheta(\bar G)\ge\sum_v(c\cdot u_v)^2\ge\frac n{\vartheta(G)+\varepsilon}
$$
である。$\varepsilon\to0$ とすればよい。
頂点推移的なときの $\le$. $\vartheta=\vartheta(G)$ とし、$\Gamma$ を自己同型群とする。2 の最大値を達成する $B$ をとり、$\sigma\in\Gamma$ について $B^\sigma_{uv}=B_{\sigma u,\sigma v}$ とおくと、$\sigma$ は隣接を保つので $B^\sigma$ も 2 の条件をみたし、$\operatorname{tr}(JB^\sigma)=\vartheta$ である。条件は凸なので平均 $\bar B=|\Gamma|^{-1}\sum_{\sigma}B^\sigma$ も 2 の条件をみたし、$\operatorname{tr}(J\bar B)=\vartheta$ で、すべての $\tau\in\Gamma$ について $\bar B_{\tau u,\tau v}=\bar B_{uv}$ である。推移性から対角成分 $\bar B_{vv}$ はすべて等しく $1/n$ であり、行和 $r_v=\sum_u\bar B_{vu}$ も $r_{\tau v}=r_v$ からすべて等しく $\vartheta/n$ である。つまり $\bar B\mathbf 1=\frac{\vartheta}n\mathbf 1$ である。
$$
M=J-\frac{n^2}{\vartheta}\bar B+\frac n{\vartheta}I
$$
とおく。対角成分は $1-\frac n\vartheta+\frac n\vartheta=1$ で、$\bar G$ で隣接しない相異なる $u,v$ は $G$ で隣接するので $\bar B_{uv}=0$、$M_{uv}=1$ である。よって $M\in\mathcal M(\bar G)$ である。$x=a\mathbf 1+y$($y\perp\mathbf 1$)と分けると、$\bar B\mathbf 1$ が $\mathbf 1$ の定数倍なので交差項は消え、
$$
x^{\mathsf T}\Bigl(\frac n\vartheta I-M\Bigr)x=\frac{n^2}{\vartheta}\bigl(a^2\,\mathbf 1^{\mathsf T}\bar B\mathbf 1+y^{\mathsf T}\bar By\bigr)-a^2n^2=\frac{n^2}{\vartheta}\,y^{\mathsf T}\bar By\ge0
$$
である($\mathbf 1^{\mathsf T}\bar B\mathbf 1=\vartheta$、$y^{\mathsf T}Jy=0$)。よって $\lambda_{\max}(M)\le n/\vartheta$、$\vartheta(\bar G)\le n/\vartheta(G)$ である。$\square$
頂点推移的な場合の等式は Knu94 §25 の定理(pp. 29–30)で、そこでも自己同型による平均を使っている。Shannon容量(グラフ) では不等式 $\vartheta(G)\vartheta(\bar G)\ge n$ だけを示し、等式は扱っていない。
一般に、頂点推移的な自己補グラフでは $\vartheta(G)=\sqrt n$ であり、$\alpha(G)\le\sqrt n\le\bar\chi(G)$ が分かる。奇閉路 $C_n$ と Petersen グラフの値は Shannon容量(グラフ) の例を参照。
グラフ $G$ がパーフェクトであるとは、$G$ のどの誘導部分グラフ $H$ でも $\chi(H)=\omega(H)$ となることをいう。パーフェクトグラフ定理 により、$G$ がパーフェクトなら $\bar G$ もパーフェクトである。
$G$ がパーフェクトなら $\vartheta(G)=\alpha(G)=\bar\chi(G)$ である。
$\bar G$ もパーフェクトなので $\chi(\bar G)=\omega(\bar G)$ であり、$\omega(\bar G)=\alpha(G)$、$\chi(\bar G)=\bar\chi(G)$ だから $\alpha(G)=\bar\chi(G)$ である。cor-lt-sandwich から $\vartheta(G)$ もこれに等しい。$\square$
Knu94 は §31(pp. 36–37)で、パーフェクトグラフについて安定集合の多面体と clique の制約による多面体が一致することを示し、そこからも同じ結論が出る。二部グラフや弦グラフはパーフェクトなので、これらのグラフの独立数は、整数 $\alpha(G)$ が $\vartheta(G)$ に等しいことから、$\vartheta(G)$ を $1/2$ 未満の誤差で計算して最も近い整数をとれば多項式時間で求まる。
| 結論 | 外した条件 | 反例 | 起きること |
|---|---|---|---|
| $\vartheta=\alpha=\bar\chi$(prop-lt-perfect) | パーフェクト | $C_5$ | $2< \sqrt5< 3$ |
| $\vartheta(G)\vartheta(\bar G)=n$(thm-lt-transitive) | 頂点推移的 | $K_{1,3}$ | $3\cdot2=6>4$ |
| 2 の最大値が有限で $\vartheta$ に等しい(thm-lt-main) | $B\succeq0$ | 辺のない 2 頂点 | $\operatorname{tr}(JB)\to\infty$ |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する