グラフと補グラフの関係 - 高温処理済みコースケ

kousuke.hatenablog.com

n頂点の完全グラフを $K_n$ 、独立グラフ(頂点のみで辺がないグラフ)を $I_n$ とする。

n頂点のグラフ $G_n$ がある。
このとき $K_n$ から $I_n$ へひとつづつ辺を消していく順序集合のうち、 $G_n$ を含む順序の集合 $F_{G_n}$ を定めることができる。

このとき $F_{G_n}$ のどの順序を通っても $G_n$ の補グラフ $G_n^\ast$ はない。
そのため $K_n \rightarrow G_n \rightarrow I_n \rightarrow G_n^\ast \rightarrow K_n$ のような構造を考えることができる。

$K_n$ の辺の数は $\frac{n(n-1)}{2}$ で $I_n$ と位相が $\pi$ ずれていて、 $2\pi$ で $K_n$ に戻るので、上の構造は $e^{i\frac{4\pi\,m}{n(n-1)}}$ と同相と考えることができそう。
同様に $G_n,G_n^\ast$ も位相が $\pi$ 離れているとみることができそう。

また最大クリーク問題を考えると頂点がなくなる方向 $K_0$ への順序集合(こちらは頂点集合)もある。
最大クリーク問題の解は $K_n \rightarrow I_n$ と $G_n \rightarrow G_n^\ast$ の方向が一致することができる最大のnとみることができる。
なんとなくグラフを複素数の多項式として表せるんじゃないかとおもっていて、上の式を頂点方向と辺方向で全微分とかすると、その極大値が最大クリークにならないだろうかとかおもっていたりする。