Polynomial Invariants of Matroids

グラフに対しては, 様々な多項式が定義されるが, その matroid への一般化も, 多くの場合得られている。まず, Tutte polynomial の一般化がある。 Gordon [Gor15] によると Crapo [Cra67] と Brylawski [Bry72] により発見された。

• Tutte polynomial of matroid

Fink と Speyer [FS12] は, matroid から \(K\)-theory の class を構成しているが, Tutte polynomial などもそれで表せるようである。

他にも色々な方法で多項式が定義される。Kung の [Kun10] の最初に, その中の次の多項式の間の関係, そして Tutte polynomial との関係が書かれている。

• characteristic polynomial [Rot64]
• subset-corank polynomial
• nullity-corank polynomial あるいは rank generating polynomial
• basis generating polynomial と independent set generating polynomial [MNY21]
• weight polynomial [JRV16]

Characteristic polynomial は, 超平面配置の characteristic polynomial と graph の chromatic polynomial 共通の拡張になっているものである。 係数の log-concavity に関する予想があったが, Huh [Huh12] により標数 \(0\) の体上で realizable な場合には証明された。その証明は hypersurface の Milnor number と関連づけるものである。 Katz との共著によるその拡張では, toric variety の intersection number, そして tropical intersection theory との関連が用いられている。

Kazhdan-Lusztig polynomial の matroid への一般化は, Elias, Proudfoot, Wakefield [EPW16] により導入されたものである。 Gedeon, Proudfoot, Young による survey [GPY17a] がある。

• Kazhdan-Lusztig polynomial [EPW16]

その equivariant version が, Gedeon, Proudfoot, Young [GPY17b] により導入されている。他にもいくつか関連した多項式が定義されている。

• equivariant Kazhdan-Lusztig polynomial
• inverse Kazhdan-Lusztig polynomial [GX21]
• \(Z\)-polynomial [PXY18]

References

[Bry72]

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

[Cra67]

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

[EPW16]

Ben Elias, Nicholas Proudfoot, and Max Wakefield. “The Kazhdan-Lusztig polynomial of a matroid”. In: Adv. Math. 299 (2016), pp. 36–70. arXiv: 1412.7408. url: https://doi.org/10.1016/j.aim.2016.05.005.

[FS12]

Alex Fink and David E. Speyer. “\(K\)-classes for matroids and equivariant localization”. In: Duke Math. J. 161.14 (2012), pp. 2699–2723. arXiv: 1004.2403. url: https://doi.org/10.1215/00127094-1813296.

[Gor15]

Gary Gordon. “Linear relations for a generalized Tutte polynomial”. In: Electron. J. Combin. 22.1 (2015), Paper 1.79, 30. arXiv: 1405. 3735.

[GPY17a]

Katie Gedeon, Nicholas Proudfoot, and Benjamin Young. “Kazhdan-Lusztig polynomials of matroids: a survey of results and conjectures”. In: Sém. Lothar. Combin. 78B (2017), Art. 80, 12. arXiv: 1611.07474.

[GPY17b]

Katie Gedeon, Nicholas Proudfoot, and Benjamin Young. “The equivariant Kazhdan-Lusztig polynomial of a matroid”. In: J. Combin. Theory Ser. A 150 (2017), pp. 267–294. arXiv: 1605. 01777. url: https://doi.org/10.1016/j.jcta.2017.03.007.

[GX21]

Alice L. L. Gao and Matthew H. Y. Xie. “The inverse Kazhdan-Lusztig polynomial of a matroid”. In: J. Combin. Theory Ser. B 151 (2021), pp. 375–392. arXiv: 2007 . 15349. url: https://doi.org/10.1016/j.jctb.2021.07.004.

[Huh12]

June Huh. “Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs”. In: J. Amer. Math. Soc. 25.3 (2012), pp. 907–927. arXiv: 1008 . 4749. url: https://doi.org/10.1090/S0894-0347-2012-00731-0.

[JRV16]

Trygve Johnsen, Jan Roksvold, and Hugues Verdure. “A generalization of weight polynomials to matroids”. In: Discrete Math. 339.2 (2016), pp. 632–645. arXiv: 1311 . 6291. url: https://doi.org/10.1016/j.disc.2015.10.005.

[Kun10]

Joseph P. S. Kung. “Convolution-multiplication identities for Tutte polynomials of graphs and matroids”. In: J. Combin. Theory Ser. B 100.6 (2010), pp. 617–624. arXiv: 0909 . 2264. url: https://doi.org/10.1016/j.jctb.2010.05.003.

[MNY21]

Satoshi Murai, Takahiro Nagaoka, and Akiko Yazawa. “Strictness of the log-concavity of generating polynomials of matroids”. In: J. Combin. Theory Ser. A 181 (2021), Paper No. 105351, 22. arXiv: 2003.09568. url: https://doi.org/10.1016/j.jcta.2020.105351.

[PXY18]

Nicholas Proudfoot, Yuan Xu, and Ben Young. “The \(Z\)-polynomial of a matroid”. In: Electron. J. Combin. 25.1 (2018), Paper No. 1.26, 21. arXiv: 1706.05575. url: https://doi.org/10.37236/7105.

[Rot64]

Gian-Carlo Rota. “On the foundations of combinatorial theory. I. Theory of Möbius functions”. In: Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964).