Polytopes from Graphs, Quivers, and Hypergraphs

凸多面体は, 様々な組み合せ論的 data から構成されるが, グラフやその一般化からも色々な方法で多面体が作られる。

E. Kim の thesis [Kim] によると, transportation polytope という種類の多面体は, operations research などでよく使われるもののようである。 また Lenz の [Len10] によると, transportation polytope は, quiver から作られる flow polytope という凸多面体の一種のようである。 Quiver から作られるものとしては, 他にも directed edge polytope と呼ばれるものもある。

• quiver の flow polytope
• transportation polytope
• directed edge polytope [OH02; Hig15]

グラフから作られたものとしては, まず associahedron の一般化の graph associahedron がある。他にも cut polytope や symmetric edge polytope など, 様々なものがある。目にしたものを挙げると以下のようになる。

• graph associahedron
• cut polytope
• stable set polytope [Chv75; Mat14] あるいは vertex packing polytope
• flow polytope [GS78]
• matching polytope [Edm65]
• root polytope [Pos09]
• Eulerian subgraph polytope [BG86; RM]
• hypergraphic polytope [BBM19]
• graphical zonotope [Gru17]
• metric polytope [DD20]
• spanning trees polytope [Cha22]
• edge polytope [OH98]
• symmetric edge polytope [Mat+11] あるいは adjacency polytope [CK; DC22]

この中で, symmetric edge polytope は, グラフの各辺を2重化してできる quiver の directed edge polytope とみなすことができる。 また, グラフに辺の長さを1として最短の道で距離を定めた有限距離空間の fundamental polytope とみなすことができる。

• fundamental polytope

2021年度修士課程修了生の高橋君が修士論文で多角形グラフの fundamental polytope の面を調べてくれたが, その内容を沼田さんが directed edge polytope に発展させたくれので [NTT] という論文になった。

Cut polytope や stable set polytope は, 全ての頂点の座標が \(0\) か \(1\) である \(0/1\)-polytope の一種である。

• \(0/1\)-polytope

Dosen と Petric [DP11] は, Postnikov ら [PRW08] の generalized permutohedron を hypergraph から得られる polytope と考えて, 一般の hypergraph から得られる polytope を調べている。

References

[BBM19]

Carolina Benedetti, Nantel Bergeron, and John Machacek. “Hypergraphic polytopes: combinatorial properties and antipode”. In: J. Comb. 10.3 (2019), pp. 515–544. arXiv: 1712.08848. url: https://doi.org/10.4310/JOC.2019.v10.n3.a4.

[BG86]

F. Barahona and M. Grötschel. “On the cycle polytope of a binary matroid”. In: J. Combin. Theory Ser. B 40.1 (1986), pp. 40–62. url: https://doi.org/10.1016/0095-8956(86)90063-8.

[Cha22]

Brahim Chaourar. “The facets of the spanning trees polytope”. In: Math. Methods Oper. Res. 96.1 (2022), pp. 113–121. arXiv: 1903. 07292. url: https://doi.org/10.1007/s00186-022-00786-w.

[Chv75]

V. Chvátal. “On certain polytopes associated with graphs”. In: J. Combinatorial Theory Ser. B 18 (1975), pp. 138–154.

[CK]

Tianran Chen and Evgeniia Korchevskaia. Graph edge contraction and subdivisions for adjacency polytopes. arXiv: 1912.02841.

[DC22]

Robert Davis and Tianran Chen. “Computing volumes of adjacency polytopes via draconian sequences”. In: Electron. J. Combin. 29.1 (2022), Paper No. 1.61, 42. arXiv: 2007 . 11051. url: https://doi.org/10.37236/9768.

[DD20]

Michel Deza and Mathieu Dutour Sikirić. “Generalized cut and metric polytopes of graphs and simplicial complexes”. In: Optim. Lett. 14.2 (2020), pp. 273–289. arXiv: 1706.02516. url: https://doi.org/10.1007/s11590-018-1358-3.

[DP11]

Kosta Došen and Zoran Petrić. “Hypergraph polytopes”. In: Topology Appl. 158.12 (2011), pp. 1405–1444. arXiv: 1010.5477. url: http://dx.doi.org/10.1016/j.topol.2011.05.015.

[Edm65]

Jack Edmonds. “Maximum matching and a polyhedron with \(0,1\)-vertices”. In: J. Res. Nat. Bur. Standards Sect. B 69B (1965), pp. 125–130.

[Gru17]

Vladimir Grujić. “Counting faces of graphical zonotopes”. In: Ars Math. Contemp. 13.1 (2017), pp. 227–234. arXiv: 1604.06931. url: https://doi.org/10.26493/1855-3974.1132.fae.

[GS78]

G. Gallo and C. Sodini. “Extreme points and adjacency relationship in the flow polytope”. In: Calcolo 15.3 (1978), pp. 277–288. url: https://doi.org/10.1007/BF02575918.

[Hig15]

Akihiro Higashitani. “Smooth Fano polytopes arising from finite directed graphs”. In: Kyoto J. Math. 55.3 (2015), pp. 579–592. arXiv: 1103.2202. url: https://doi.org/10.1215/21562261-3089073.

[Kim]

Edward D. Kim. Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method. arXiv: 1006. 2416.

[Len10]

Matthias Lenz. “Toric ideals of flow polytopes”. 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. 889–896. arXiv: 0801.0495.

[Mat+11]

Tetsushi Matsui, Akihiro Higashitani, Yuuki Nagazawa, Hidefumi Ohsugi, and Takayuki Hibi. “Roots of Ehrhart polynomials arising from graphs”. In: J. Algebraic Combin. 34.4 (2011), pp. 721–749. arXiv: 1003.5444. url: https://doi.org/10.1007/s10801-011-0290-8.

[Mat14]

Kazunori Matsuda. “Strong Koszulness of toric rings associated with stable set polytopes of trivially perfect graphs”. In: J. Algebra Appl. 13.4 (2014), pp. 1350138, 11. arXiv: 1308 . 5461. url: https://doi.org/10.1142/S0219498813501387.

[NTT]

Yasuhide Numata, Yusuke Takahashi, and Dai Tamaki. Faces of Directed Edge Polytopes. arXiv: 2203.14521.

[OH02]

Hidefumi Ohsugi and Takayuki Hibi. “Hamiltonian tournaments and Gorenstein rings”. In: European J. Combin. 23.4 (2002), pp. 463–470. url: http://dx.doi.org/10.1006/eujc.2002.0572.

[OH98]

Hidefumi Ohsugi and Takayuki Hibi. “Normal polytopes arising from finite graphs”. In: J. Algebra 207.2 (1998), pp. 409–426. url: http://dx.doi.org/10.1006/jabr.1998.7476.

[Pos09]

Alexander Postnikov. “Permutohedra, associahedra, and beyond”. In: Int. Math. Res. Not. IMRN 6 (2009), pp. 1026–1106. arXiv: math/0507163. url: https://doi.org/10.1093/imrn/rnn153.

[PRW08]

Alex Postnikov, Victor Reiner, and Lauren Williams. “Faces of generalized permutohedra”. In: Doc. Math. 13 (2008), pp. 207–273. arXiv: math/0609184.

[RM]

Tim Römer and Sara Saeedi Madani. Cycle algebras and polytopes of matroids. arXiv: 2105.00185.