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

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

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

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

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

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

多面体の scissors congruence group は, Zakharevich [Zak12] により algebraic \(K\)-theory spectrum として一般化 (高次化) されたが, その構成は, cut-and-paste \(K\)-theory として, 更に一般化されている。 その matroid 版は, Tutte polynomial との関係も含め, Gomez Lopez の [Gom] で調べられている。 そこで使われているのは, Bohmann ら [Boh+24] の category with covering family に対する \(K\)-theory であるが。

References

[ACH15]

Federico Ardila, Federico Castillo, and Michael Henley. “The arithmetic Tutte polynomials of the classical root systems”. In: Int. Math. Res. Not. IMRN 12 (2015), pp. 3830–3877. arXiv: 1305.6621. url: https://doi.org/10.1093/imrn/rnu050.

[Ard]

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

[BKP22]

Olivier Bernardi, Tamás Kálmán, and Alexander Postnikov. “Universal Tutte polynomial”. In: Adv. Math. 402 (2022), Paper No. 108355, 74. arXiv: 2004.00683. url: https://doi.org/10.1016/j.aim.2022.108355.

[Boh+24]

Anna Marie Bohmann, Teena Gerhardt, Cary Malkiewich, Mona Merling, and Inna Zakharevich. “A trace map on higher scissors congruence groups”. In: Int. Math. Res. Not. IMRN 18 (2024), pp. 12683–12710. arXiv: 2303.08172. url: https://doi.org/10.1093/imrn/rnae153.

[Bry72]

T. H. Brylawski. “The Tutte-Grothendieck ring”. In: Algebra Universalis 2 (1972), pp. 375–388. url: https://doi.org/10.1007/BF02945050.

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

[Gom]

Mauricio Gomez Lopez. Realizing the Tutte polynomial as a cut-and-paste \(K\)-theoretic invariant. arXiv: 2501.12250.

[Gor15]

Gary Gordon. “Linear relations for a generalized Tutte polynomial”. In: Electron. J. Combin. 22.1 (2015), Paper 1.79, 30. 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.

[Zak12]

Inna Zakharevich. “Scissors congruence as \(K\)-theory”. In: Homology Homotopy Appl. 14.1 (2012), pp. 181–202. arXiv: 1101.3833. url: https://doi.org/10.4310/HHA.2012.v14.n1.a9.