Polymatroid

Polymatroid とは, matroid の multiset 版である。 Derksen と Fink の [DF10] によると, 1960年代後半 [Edm70] には考えられていたようである。

Castillo と Liu [CL22] は, Edmonds の論文 [Edm70] と Fujishige の本 [Fuj05] を参照している。 Edmonds の論文は, Lecture Notes in Computer Science の中の [JRR03] に収録されている。

Edmonds のは, 係数を非負の実数にとるもので, 係数が \(0\) か \(1\) の場合が通常の matroid になる。Herzog と Hibi は, 非負の整数に値を持つものを discrete polymatroid として [HH02] で考えている。

• discrete polymatroid

Matroid には, 実に様々な公理 (特徴付け) があるが, polymatroid に対しても, 様々な公理がある。それらの同値性は, 上記の Herzog と Hibi の論文で証明されている。

Matroid からは matroid base polytope として, convex polytope を作ることができるが, polymatroid に対しても polymatroid base polytope を作ることができる。

• polymatroid base polytope

Lam と Postnikov [LP24] によると, polymatroid は, 本質的には, generalized permutohedron と同じもののようである。

Tutte polynomial などの不変量も polymatroid に一般化されている。 Tutte polynomial については, Bernardi, Kalman, Postnikov の [BKP22] で導入されている。

• Tutte polynomial for polymatroid

Kálmán [Kál13] は, Tutte polynomial の specialization の一般化として exterior polynomial と interior polynomial を導入しているが, Guan, Yang, Jin [GYJ24] は, その結果の polymatroid の Tutte polynomial への一般化を証明している。

Quasisymmetric function については, Derksen の [Der09] で導入されている。

• quasisymmetric function for polymatroid

Bergman fan も matroid に対して定義されるものであるが, それを polymatroid に一般化したものとしては, Crowley らの [Cro+] がある。

• Bergman fan of polymatroid

Chow ring は, Pagaria と Pezzoli [PP23] により定義されている。

• Chow ring of polymatroid

Matroid に対しては, \(q\)-analogue として \(q\)-matroid の概念があるが, polymatroid についても Jurrius と Gorla と López と Ravagnani [Gor+20] により, \(q\)-polymatroid の概念が導入されている。

• \(q\)-polymatroid

References

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

[CL22]

Federico Castillo and Fu Liu. “Deformation cones of nested braid fans”. In: Int. Math. Res. Not. IMRN 3 (2022), pp. 1973–2026. arXiv: 1710.01899. url: https://doi.org/10.1093/imrn/rnaa090.

[Cro+]

Colin Crowley, June Huh, Matt Larson, Connor Simpson, and Botong Wang. The Bergman fan of a polymatroid. arXiv: 2207.08764.

[Der09]

Harm Derksen. “Symmetric and quasi-symmetric functions associated to polymatroids”. In: J. Algebraic Combin. 30.1 (2009), pp. 43–86. arXiv: 0801.4393. url: http://dx.doi.org/10.1007/s10801-008-0151-2.

[DF10]

Harm Derksen and Alex Fink. “Valuative invariants for polymatroids”. In: 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010). Discrete Math. Theor. Comput. Sci. Proc., AN. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2010, pp. 271–282. arXiv: 0908.2988.

[Edm70]

Jack Edmonds. “Submodular functions, matroids, and certain polyhedra”. In: Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969). New York: Gordon and Breach, 1970, pp. 69–87.

[Fuj05]

Satoru Fujishige. Submodular functions and optimization. Second. Vol. 58. Annals of Discrete Mathematics. Elsevier B. V., Amsterdam, 2005, pp. xiv+395. isbn: 0-444-52086-4.

[Gor+20]

Elisa Gorla, Relinde Jurrius, Hiram H. López, and Alberto Ravagnani. “Rank-metric codes and \(q\)-polymatroids”. In: J. Algebraic Combin. 52.1 (2020), pp. 1–19. arXiv: 1803.10844. url: https://doi.org/10.1007/s10801-019-00889-4.

[GYJ24]

Xiaxia Guan, Weiling Yang, and Xian’an Jin. “On the polymatroid Tutte polynomial”. In: J. Combin. Theory Ser. A 201 (2024), Paper No. 105798, 14. arXiv: 2207.04421. url: https://doi.org/10.1016/j.jcta.2023.105798.

[HH02]

Jürgen Herzog and Takayuki Hibi. “Discrete polymatroids”. In: J. Algebraic Combin. 16.3 (2002), 239–268 (2003). arXiv: math/0307236. url: http://dx.doi.org/10.1023/A:1021852421716.

[JRR03]

Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi, eds. Combinatorial optimization—Eureka, you shrink! Vol. 2570. Lecture Notes in Computer Science. Papers dedicated to Jack Edmonds, Papers from the 5th International Workshop held in Aussois, March 5–9, 2001. Springer-Verlag, Berlin, 2003, pp. x+209. isbn: 3-540-00580-3. url: https://doi.org/10.1007/3-540-36478-1.

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

[LP24]

Thomas Lam and Alexander Postnikov. “Polypositroids”. In: Forum Math. Sigma 12 (2024), Paper No. e42, 67. arXiv: 2010.07120. url: https://doi.org/10.1017/fms.2024.11.

[PP23]

Roberto Pagaria and Gian Marco Pezzoli. “Hodge theory for polymatroids”. In: Int. Math. Res. Not. IMRN 23 (2023), pp. 20118–20168. arXiv: 2105.04214. url: https://doi.org/10.1093/imrn/rnad001.