グラフは2次形式、とか考えてみる

変数集合を \(V=\{v_1, \ldots, v_n\}\) とする。 適当な環 \(R\) をとり、多項式環 \(R[V]\) を考える。 この中の2次斉次多項式、つまり2次形式をグラフということにする。

\[g = \sum a_{ij}v_i v_j\]

\(V\) はもちろん頂点集合と考える。 \(a_{ij} \neq 0\) のとき、積 \(v_i v_j\) をグラフ \(g\) の辺といい、頂点 \(v_i\) と \(v_j\) は隣接するという。 辺 \(v_i^2\) をループと呼ぶ。 \(g\) が \(V\) の真部分集合 \(V'\) 上の多項式環 \(R[V']\) に含まれないとき、\(|V|\) を \(g\) の位数という。 ここで一つ注意として、\(a_{ij}\) は一番簡単な設定では \({0, 1}\) にしか値をとらないので整数と考えればいいが、 辺に何らかの値を持たせる (「2本ある」とか「容量が2.5」とか)必要があるときに \(a_{ij}\) の値としてコード化する役割を担うため、 係数環 \(R\) の選択の余地を残してある。 これは係数 2 を重複した辺の本数と思うか、割り振られた容量が 2 と思うかは解釈次第だし、 両方の情報を盛り込みたいと思ったら、係数も多項式環みたいなものを使って分けて考えるようにするのは自分の責任ですよ、という割り切りを意味している。

手始めに彩色数を考えてみる。 頂点に色を塗るのだが、隣接する頂点には別の色を塗らなければいけないという制約を付けるとき最低限必要な色数のこと。 係数環は \(\mathbb{Z}\) で良い。 色の集合 \(C_m\) を \(\{c_1, \ldots, c_m\}\) という集合とする(\(m\) はパラメータ)。 \(g\) の各頂点 \(v_i\) に色 \(c_j\) を対応させると、自然に多項式環の準同型 \(\phi: \mathbb{Z}[V] \rightarrow \mathbb{Z}[C_m]\) が定まる。 気付けば像もグラフになっている。 先程の「隣接する頂点には別の色」というのは、辺の像がループにならないということだ。 実は彩色数とは"グラフの準同型写像"でループができない最小の像の位数、みたいな言い方ができたのだ。 というのが今日の気付き。

以下余談というかあとがきというか。 世の中には代数的グラフ理論という分野があって、グラフは行列、ということで推し進められている。 プログラムのデータ構造的にも確かに似たようなものなので納得できるのではあるが、 有向グラフの特殊ケースとして無向グラフがあるように見えて(つまり対称行列だけが無向グラフという限定の方向)、ちょっと気持ち悪い。 その点、多項式方式は始めから無向だし(変数の積の可換性を仮定すれば)、ハイパーグラフは次数を上げるだけだし、どうだろう。 ちなみに、2次形式は行列、という見方も一般的なので、実際のところ何ら広がっていないのかもしれない。