Polymatroid

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

Castillo と Liu [CL22] は, Edmond の survey [Edm70] と Fujishige の本 [Fuj05] を参照している。

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

• discrete polymatroid

Polymatroid に対しても, 様々な公理がある。それらの同値性は, 上記の Herzog と Hibi の論文で証明されている。

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

• polymatroid base polytope

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

Tutte polynomial や quasisymmetric function などの不変量も polymatroid に一般化されている。 Tutte polynomial については, Bernardi, Kalman, Postnikov の [BKP22], quasisymmetric function については, Derksen の [Der09] など。

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.

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

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

[LP]

Thomas Lam and Alexander Postnikov. Polypositroids. arXiv: 2010. 07120.