接続行列

昔書いた論文 (末尾参照) の前半部分は何だか無駄が多かったような気がふいに湧いてきました。

無向グラフの接続行列を考えます。 辺 \(e_j\) が頂点 \(v_{i}\) と \(v_{i'}\) に接続しているとき、\(i,j\) 成分と \(i',j\) 成分に \(1\) が入り、 \(j\) 列目の残りの成分は \(0\) となるような行列です。

接続行列の核、つまりこの接続行列を(\(\mathbb{Q}\) 上)線型写像だと思った時の核は、長さが偶数の閉じた道に対応します。 ここでいう「道」は、同じ頂点や辺を通ってもいいけど同一の辺への折り返しは無し、です。 なぜそうなるかは、核が「辺に数を割り当てたときに接続する各頂点上で和が 0 になるものを集めたもの」だからです。 たとえば長さが偶数しか出てこないのは正と負がバランスするためだし、折り返しができないのは折り返しの前後の同じ辺に正と負を同時には割り振れないからです。

というようなことが、グラフ理論の本にはなかなか出てこないような気がして一応書いています(もちろん知られている議論です)。 \(\mathbb{F}_2\) 上での核がサイクルに対応します、みたいな命題は見ますが。

次に、ハイパーグラフで同じように考えます。 接続行列・頂点・辺という用語をそのまま流用します。 ハイパーグラフの接続行列とは、辺 \(e_j\) が頂点 \(v_{i_0}, \ldots, v_{i_k}\) に接続しているとき、\(i_0,j\) 成分, \(\ldots\), \(i_k,j\) 成分に \(1\) が入り、 \(j\) 列目の残りの成分は \(0\) となるような行列です。

考えたいハイパーグラフは、無向グラフの共通頂点を持たない奇サイクル二つを合わせたものを一つの辺として追加したようなものです。 この辺に \(2\) を割り当てて、元にした奇サイクル上の辺にそれぞれ \(-1\) を割り当てるとハイパーグラフの接続行列の核に入ります。 いわばこの関係が追加する辺の定義です。 他にも追加した辺に関わる関係式が「接続行列の核を計算するだけで」手に入ります。 グラフに対する閉じた道のような一言で説明できる何かに対応しているわけではないですが、議論は完全に同じように進みます。

論文ではこういう方法を採らずに多項式の用語で、生成系に入る二項式の形を挙げていってこれで十分、みたいなことをやっていました。

Matsui, T. "Ehrhart Series for Connected Simple Graphs" Graphs and Combinatorics (2013) 29: 617. https://doi.org/10.1007/s00373-011-1126-y