グラフの多項式不変量

グラフに対し多項式を定義し, その性質を調べることにより元のグラフの性質を得るというのは, 結び目を多項式で調べる手法と似ている。 このような graph polynomial については, Ellis-Monaghan と Merino の survey [EM11a; EM11b] がある。

有名な graph polynomial として chromatic polynomial がある。 その変種も色々ある。

• chromatic polynomial とその変種

他にも様々な多項式が考えられている。

• Yamada polynomial ([Yam89])
• vertex-nullity interlace polynomial ([ABS04])
• two-variable interlace polynomial ([AH04])
• multivariate interlace polynomial ([Trad])
• bracket polynomial ([TZ; Trab; Trac; Traa])
• edge-elimination polynomial ([AGM10])

Ellis-Monaghan と Merino の [EM11a] によると, そのような多項式の中で deletion/contraction reduction を持つものについては, Tutte polynomial が最も universal なものらしい。それを ribbon graph に一般化した Bollobas-Riordan polynomial というものもある。

• Tutte polynomial
• Bollobas-Riordan polynomial
• ribbon graph に対する多項式不変量

これらの多項式不変量は, Khovanov の Jones polynomial のcategorification を真似て, categorify することができる。

• グラフ多項式の categorification

このような類似性から, グラフの多項式不変量と結び目の多項式不変量の直接 の関係を調べるというのは, 自然な問題である。実際 Huggett と Moffatt の [HM] によると, [Thi87; Jae88; Hug05; Mof; Das+08; CP07; CV08] などがある。

多項式があれば, その零点を考えたくなる。

• グラフの多項式の零点

Tutte polynomial は 統計物理学の Potts model と関係が深い。また Ising model の partition function の特別な場合として, Ising polynomial という2あるいは3変数の多項式も定義されている。 Kotekの [Kot] など。

• Ising polynomial

Chromatic polynomial や flow polynomial は arrangement の characteristic polynomial として表わすことができる。 この視点から, chromatic polynomial の係数の log-concavity に関する予想を証明しているのは, Huh の [Huh], そして Katz との共著によるその拡張 [HK] である。特異点論や toric variety と関連づけて証明していて興味深い。

Tutte polynomial を, subspace arrangement の characteristic polynomial として表わせないかという問題を考えているのは, Beifang Chen [Che10] である。

• graph や hypergraph からできる arrangement (graphic arrangement)

また, Eastwood と Huggett [EH07] は, configuration space が braid arrangement の一般化であることに着目し, graphic arrangement を configuration space に一般化したものを考えている。 空間として複素射影空間を取ると, その Euler標数として, 元のグラフの chromatic polynomial が得られることを示している。

他にも, chromatic polynomial の解釈としては, Kac-Moody Lie algebra を用いたもの [VV] もある。

Graph の多項式を hypergraph に対して拡張しようと考えるのは当然であるが, 更に simplicial complex や CW complex への一般化も考えられている。 Møller と Nord の[MN] や Beck と Breuer と Godkin と Martin の [Bec+14] などである。 後者では, chromatic polynomial や flow polynomial などの一般化が任意のCW複体に対し定義されている。

グラフの辺を変数として定義されたグラフとして, Kirchhoff polynomial がある。

• Kirchhoff polynomial

その零点は, affine space の中の hypersurface になるので, 代数幾何学的視点から調べることが考えられる。 実際, グラフとして Feynman graph をとったときが, Feynman motive の理論として研究されている。

• Feynman motive

例えば, Marcolli と Tabuada の [MT] の Introduction で挙げられている文献を見るとよい。この手の話の最初は, Bloch, Esnault, Kreimer の [BEK06] のようである。

全く異なるアイデアに基づいた多項式の構成としては, Leinster の graph の magnitude [Lei] がある。

• graph の magnitude

名前が示すように, 彼の導入した metric space の magnitude, よって small category の Euler 標数, のアイデアに基づくものである。 また, その categorification が Hepworth と Willerton [HW] により発見されている。

References

[ABS04]

Richard Arratia, Béla Bollobás, and Gregory B. Sorkin. “The interlace polynomial of a graph”. In: J. Combin. Theory Ser. B 92.2 (2004), pp. 199–233. arXiv: math/0209045. url: http://dx.doi.org/10.1016/j.jctb.2004.03.003.

[AGM10]

Ilia Averbouch, Benny Godlin, and J. A. Makowsky. “An extension of the bivariate chromatic polynomial”. In: European J. Combin. 31.1 (2010), pp. 1–17. url: http://dx.doi.org/10.1016/j.ejc.2009.05.006.

[AH04]

Martin Aigner and Hein van der Holst. “Interlace polynomials”. In: Linear Algebra Appl. 377 (2004), pp. 11–30. url: http://dx.doi.org/10.1016/j.laa.2003.06.010.

[Bec+14]

Matthias Beck, Felix Breuer, Logan Godkin, and Jeremy L. Martin. “Enumerating colorings, tensions and flows in cell complexes”. In: J. Combin. Theory Ser. A 122 (2014), pp. 82–106. arXiv: 1212.6539. url: https://doi.org/10.1016/j.jcta.2013.10.002.

[BEK06]

Spencer Bloch, Hélène Esnault, and Dirk Kreimer. “On motives associated to graph polynomials”. In: Comm. Math. Phys. 267.1 (2006), pp. 181–225. arXiv: math/0510011. url: http://dx.doi.org/10.1007/s00220-006-0040-2.

[Che10]

Beifang Chen. “Orientations, lattice polytopes, and group arrangements. I. Chromatic and tension polynomials of graphs”. In: Ann. Comb. 13.4 (2010), pp. 425–452. arXiv: 1007.2453. url: http://dx.doi.org/10.1007/s00026-009-0037-6.

[CP07]

Sergei Chmutov and Igor Pak. “The Kauffman bracket of virtual links and the Bollobás-Riordan polynomial”. In: Mosc. Math. J. 7.3 (2007), pp. 409–418, 573. arXiv: math/0609012.

[CV08]

Sergei Chmutov and Jeremy Voltz. “Thistlethwaite’s theorem for virtual links”. In: J. Knot Theory Ramifications 17.10 (2008), pp. 1189–1198. arXiv: 0704.1310. url: http://dx.doi.org/10.1142/S0218216508006609.

[Das+08]

Oliver T. Dasbach, David Futer, Efstratia Kalfagianni, Xiao-Song Lin, and Neal W. Stoltzfus. “The Jones polynomial and graphs on surfaces”. In: J. Combin. Theory Ser. B 98.2 (2008), pp. 384–399. arXiv: math/0605571. url: http://dx.doi.org/10.1016/j.jctb.2007.08.003.

[EH07]

Michael Eastwood and Stephen Huggett. “Euler characteristics and chromatic polynomials”. In: European J. Combin. 28.6 (2007), pp. 1553–1560. url: http://dx.doi.org/10.1016/j.ejc.2006.09.005.

[EM11a]

Joanna A. Ellis-Monaghan and Criel Merino. “Graph polynomials and their applications I: The Tutte polynomial”. In: Structural analysis of complex networks. Birkhäuser/Springer, New York, 2011, pp. 219–255. arXiv: 0803.3079. url: https://doi.org/10.1007/978-0-8176-4789-6_9.

[EM11b]

Joanna A. Ellis-Monaghan and Criel Merino. “Graph polynomials and their applications II: Interrelations and interpretations”. In: Structural analysis of complex networks. Birkhäuser/Springer, New York, 2011, pp. 257–292. arXiv: 0806.4699. url: https://doi.org/10.1007/978-0-8176-4789-6_10.

[HK]

June Huh and Eric Katz. Log-concavity of characteristic polynomials and the Bergman fan of matroids. arXiv: 1104.2519.

[HM]

Stephen Huggett and Iain Moffatt. Expansions for the Bollobas-Riordan polynomial of separable ribbon graphs. arXiv: 0710.4266.

[Hug05]

Stephen Huggett. “On tangles and matroids”. In: J. Knot Theory Ramifications 14.7 (2005), pp. 919–929. url: http://dx.doi.org/10.1142/S0218216505004147.

[Huh]

June Huh. Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. arXiv: 1008.4749.

[HW]

Richard Hepworth and Simon Willerton. Categorifying the magnitude of a graph. arXiv: 1505.04125.

[Jae88]

François Jaeger. “Tutte polynomials and link polynomials”. In: Proc. Amer. Math. Soc. 103.2 (1988), pp. 647–654. url: http://dx.doi.org/10.2307/2047194.

[Kot]

Tomer Kotek. Complexity of Ising Polynomials. arXiv: 1110.3639.

[Lei]

Tom Leinster. The magnitude of a graph. arXiv: 1401.4623.

[MN]

Jesper Møller and Gesche Nord. Chromatic polynomials of simplicial complexes. arXiv: 1212.0305.

[Mof]

Iain Moffatt. Knot invariants and the Bollobas-Riordan polynomial of embedded graphs. arXiv: math/0605466.

[MT]

Matilde Marcolli and Goncalo Tabuada. Feynman quadrics-motive of the massive sunset graph. arXiv: 1705.10307.

[Thi87]

Morwen B. Thistlethwaite. “A spanning tree expansion of the Jones polynomial”. In: Topology 26.3 (1987), pp. 297–309. url: http://dx.doi.org/10.1016/0040-9383(87)90003-6.

[Traa]

Lorenzo Traldi. A bracket polynomial for graphs, IV. Undirected Euler circuits, graph-links and multiply marked graphs. arXiv: 1003.1560.

[Trab]

Lorenzo Traldi. A bracket polynomial for graphs. II. Links, Euler circuits and marked graphs. arXiv: 0901.1451.

[Trac]

Lorenzo Traldi. A bracket polynomial for graphs. III. Vertex weights. arXiv: 0905.4879.

[Trad]

Lorenzo Traldi. On the interlace polynomials. arXiv: 1008.0091.

[TZ]

L. Traldi and L. Zulli. A bracket polynomial for graphs. arXiv: 0808.3392.

[VV]

R. Venkatesh and Sankaran Viswanath. Chromatic polynomials of graphs from Kac-Moody algebras. arXiv: 1303.1148.

[Yam89]

Shuji Yamada. “An invariant of spatial graphs”. In: J. Graph Theory 13.5 (1989), pp. 537–551.