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

Tutte polynomial は, graph に対し Tutte により定義された多項式であるが, その定義は, matroid へ拡張できる。 Gordon [Gor] によると, そのような拡張は, Crapo [Cra67] と Brylawski [Bry72] により発見されたようである。 その定義は, 例えば, Eschenbrenner と Falk の [EF99] にも書かれている。

Matroid に対し定義が拡張されたことで, graph 以外の幅広い組み合せ論的構造に対して, Tutte polynomial が定義されたことになる。

例えば, hyperplane arrangement の Tutte polynomial については, Ardila, Castillo, Henley の [ACH] や Aridila による survey [Ard] を見るとよい。

Matroid には様々な変種があるが, Tutte polynomial もそのいくつかに対し一般化されている。例えば, 以下のようなものがある。

• multiplicity matroid に対する multiplicity Tutte polynomial [Moc12]
• greedoid や antimatroid に対する一般化 [CG91]
• polymatroid に対する一般化 [BKP]

References

[ACH]

Federico Ardila, Federico Castillo, and Michael Henley. The arithmetic Tutte polynomials of the classical root systems. arXiv: 1305.6621.

[Ard]

Federico Ardila. Tutte polynomials of hyperplane arrangements and the finite field method. arXiv: 1710.01424.

[BKP]

Olivier Bernardi, Tamas Kalman, and Alex Postnikov. Universal Tutte polynomial. arXiv: 2004.00683.

[Bry72]

T. H. Brylawski. “The Tutte-Grothendieck ring”. In: Algebra Universalis 2 (1972), pp. 375–388.

[CG91]

Sharad Chaudhary and Gary Gordon. “Tutte polynomials for trees”. In: J. Graph Theory 15.3 (1991), pp. 317–331. url: http://dx.doi.org/10.1002/jgt.3190150308.

[Cra67]

Henry H. Crapo. “A higher invariant for matroids”. In: J. Combinatorial Theory 2 (1967), pp. 406–417.

[EF99]

Carrie J. Eschenbrenner and Michael J. Falk. “Orlik-Solomon algebras and Tutte polynomials”. In: J. Algebraic Combin. 10.2 (1999), pp. 189–199. arXiv: math/9805128. url: http://dx.doi.org/10.1023/A:1018735815621.

[Gor]

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

[Moc12]

Luca Moci. “A Tutte polynomial for toric arrangements”. In: Trans. Amer. Math. Soc. 364.2 (2012), pp. 1067–1088. arXiv: 0911.4823. url: http://dx.doi.org/10.1090/S0002-9947-2011-05491-7.