Polytopes from Graphs, Quivers, and Hypergraphs

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

E. Kim の thesis [Kim] によると, transportation polytope という種類の多面体は, operations research などでよく使われるもののようである。 また Lenz の [Len] によると, 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 などがある。

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

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

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

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

References

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

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

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

[Len]

Matthias Lenz. Toric Ideals of Flow Polytopes. arXiv: 0801.0495.

[Mat]

Kazunori Matsuda. Strong Koszulness of toric rings associated with stable set polytopes of trivially perfect graphs. arXiv: 1308.5461.

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

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

[PRW08]

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