Tutte polynomial

グラフの多項式不変量にも色々あるが, その中でも代表的なものの一つが, Tutte polynomial である。 Ellis-Monaghan と Merinoのsurvey [EM] によると, Tutte polynomial は Tutte [Tut47; Tut54; Tut67] により導入された。

• グラフの Tutte polynomial

White の [Whi] によると, Brylawski と Oxley の [BO92] を見るのがよいようである。 また, Gordon [Gor] は, Tutte がどのように Tutte polynomial の定義を思い付いたかについて, Tutte の [Tut04] を読むことを勧めている。

Tutte polynomial は, 結び目の不変量と深い関係にある。 Thistlethwaite の [Thi87], Jaeger の [Jae88], Moffatt らの [LM] など。

Beaudin らの [Bea+10] によると, Tutte polynomial は, statistical mechanics の Potts model と関係があるらしい。この関係の解説としては, Welsh と Merino の [WM00] もある。 この MathOverflow の質問に対する Westbury の回答では, Baxter の本 [Bax89] と Sokal らの論文 [Sok05; SS10; JS09] が挙げられている。

Ribbon graph に対する一般化は, Bollobas-Riordan polynomial という。

• Bollobas-Riordan polynomial

Hypergraph への一般化を考えているのは, Kálmán [Kál13] である。

別の方向での高次元化, つまりcell complex への一般化は, Krushkal と Renardy [KR] により定義されている。 Bajo と Burdick と Chumutov [BBC] は, 他の cell complex の不変量との比較を行なっている。Bott が [Bot52] で定義し, [Bot93] で復活した Bott polynomial と関係があるようである。

• Tutte-Krushkal-Renardy polynomial

Hiraoka と Shirai は, [HS]で, この一般化された Tutte polynomial を用いて, ある random cell complex の model を調べている。

Matroid の不変量にも一般化されている。 Matroidは様々な構造を一般化するため, それにより Tutte polynomial がグラフ以外の幅広い組み合せ論的構造に対して, 定義されたことになる。例えば, hyperplane arrangement など。

• matroid やその一般化に対する Tutte polynomial

Awan と Bernardi [AB] は, quiver への一般化を \(B\)-polynomial として提案している。彼等は, graph の double としてできる quiver に対しては, \(B\)-polynomial が元の graph の Tutte polynomial と一致するので, 正しい一般化であると主張している。

• quiver の \(B\)-polynomial

向き付け可能な曲面に埋め込まれたグラフ, つまり map に対する一般化が Goodall, Krajewski, Regt, Vena [Goo+] により導入されている。

• surface Tutte polynomial

このように, 様々な変種が考えられているため, これらを統一しようと考える人が現われても不思議ではない。 Matroid の Tutte polynomial がそのような試みの一つである。 他にも, combinatorial Hopf algebra を用いて, contraction と deletion を持つ組み合せ論的構造に対し定義されている Tutte polynomial を一括して扱うことを, Krajewski と Moffatt と Tanasa [KMT] が提案している。

• combinatorial Hopf algebra の Tutte polynomial

このような多項式があると, Jones polynomial のように categorification を考えたくなる。 Tutte polynomial の categorification を考えているのは, Jasso-Hernandez と Rong [JR06] である。Hyperplane arrangement の Tutte polynomial の categorification は Dancso と Licata [DL] により考えられている。

References

[AB]

Jordan Awan and Olivier Bernardi. Tutte Polynomials for Directed Graphs. arXiv: 1610.01839.

[Bax89]

Rodney J. Baxter. Exactly solved models in statistical mechanics. Reprint of the 1982 original. London: Academic Press Inc. [Harcourt Brace Jovanovich Publishers], 1989, pp. xii+486. isbn: 0-12-083182-1.

[BBC]

Carlos Bajo, Bradley Burdick, and Sergei Chmutov. On the Tutte-Krushkal-Renardy polynomial for cell complexes. arXiv: 1204.3563.

[Bea+10]

Laura Beaudin, Joanna Ellis-Monaghan, Greta Pangborn, and Robert Shrock. “A little statistical mechanics for the graph theorist”. In: Discrete Math. 310.13-14 (2010), pp. 2037–2053. arXiv: 0804.2468. url: http://dx.doi.org/10.1016/j.disc.2010.03.011.

[BO92]

Thomas Brylawski and James Oxley. “The Tutte polynomial and its applications”. In: Matroid applications. Vol. 40. Encyclopedia Math. Appl. Cambridge: Cambridge Univ. Press, 1992, pp. 123–225. url: http://dx.doi.org/10.1017/CBO9780511662041.007.

[Bot52]

Raoul Bott. “Two new combinatorial invariants for polyhedra”. In: Portugaliae Math. 11 (1952), pp. 35–40.

[Bot93]

Raoul Bott. “Reflections on the theme of the poster”. In: Topological methods in modern mathematics (Stony Brook, NY, 1991). Houston, TX: Publish or Perish, 1993, pp. 125–135.

[DL]

Zsuzsanna Dancso and Anthony Licata. Odd Khovanov Homology for Hyperplane Arrangements. arXiv: 1205.2784.

[EM]

Joanna Ellis-Monaghan and Criel Merino. Graph polynomials and their applications I: The Tutte polynomial. arXiv: 0803.3079.

[Goo+]

Andrew Goodall, Thomas Krajewski, Guus Regts, and Lluis Vena. A Tutte polynomial for maps. arXiv: 1610.04486.

[Gor]

Gary Gordon. Linear relations for a generalized Tutte polynomial. arXiv: 1405.3735.

[HS]

Yasuaki Hiraoka and Tomoyuki Shirai. Tutte polynomials and random-cluster models in Bernoulli cell complexes. arXiv: 1602.04561.

[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.

[JR06]

Edna F. Jasso-Hernandez and Yongwu Rong. “A categorification for the Tutte polynomial”. In: Algebr. Geom. Topol. 6 (2006), 2031–2049 (electronic). arXiv: math/0512613. url: http://dx.doi.org/10.2140/agt.2006.6.2031.

[JS09]

Bill Jackson and Alan D. Sokal. “Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids”. In: J. Combin. Theory Ser. B 99.6 (2009), pp. 869–903. arXiv: 0806.3249. url: http://dx.doi.org/10.1016/j.jctb.2009.03.002.

[Kál13]

Tamás Kálmán. “A version of Tutte’s polynomial for hypergraphs”. In: Adv. Math. 244 (2013), pp. 823–873. arXiv: 1103.1057. url: https://doi.org/10.1016/j.aim.2013.06.001.

[KMT]

Thomas Krajewski, Iain Moffatt, and Adrian Tanasa. Hopf algebras and Tutte polynomials. arXiv: 1508.00814.

[KR]

Vyacheslav Krushkal and David Renardy. A polynomial invariant and duality for triangulations. arXiv: 1012.1310.

[LM]

Martin Loebl and Iain Moffatt. The chromatic polynomial of fatgraphs and its categorification. arXiv: math/0511557.

[Sok05]

Alan D. Sokal. “The multivariate Tutte polynomial (alias Potts model) for graphs and matroids”. In: Surveys in combinatorics 2005. Vol. 327. London Math. Soc. Lecture Note Ser. Cambridge: Cambridge Univ. Press, 2005, pp. 173–226. arXiv: math/0503607. url: http://dx.doi.org/10.1017/CBO9780511734885.009.

[SS10]

Alexander D. Scott and Alan D. Sokal. “Some variants of the exponential formula, with application to the multivariate Tutte polynomial (alias Potts model)”. In: Sém. Lothar. Combin. 61A (2009/10), Art. B61Ae, 33. arXiv: 0803.1477.

[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.

[Tut04]

W. T. Tutte. “Graph-polynomials”. In: Adv. in Appl. Math. 32.1-2 (2004). Special issue on the Tutte polynomial, pp. 5–9. url: http://dx.doi.org/10.1016/S0196-8858(03)00041-1.

[Tut47]

W. T. Tutte. “A ring in graph theory”. In: Proc. Cambridge Philos. Soc. 43 (1947), pp. 26–40. url: https://doi.org/10.1017/s0305004100023173.

[Tut54]

W. T. Tutte. “A contribution to the theory of chromatic polynomials”. In: Canadian J. Math. 6 (1954), pp. 80–91. url: https://doi.org/10.4153/cjm-1954-010-9.

[Tut67]

W. T. Tutte. “On dichromatic polynominals”. In: J. Combinatorial Theory 2 (1967), pp. 301–320.

[Whi]

Jacob A White. On Multivariate Chromatic Polynomials of Hypergraphs and Hyperedge Elimination. arXiv: 1012.3423.

[WM00]

D. J. A. Welsh and C. Merino. “The Potts model and the Tutte polynomial”. In: J. Math. Phys. 41.3 (2000). Probabilistic techniques in equilibrium and nonequilibrium statistical physics, pp. 1127–1152. url: http://dx.doi.org/10.1063/1.533181.