グラフからできる多面体

グラフからは, 様々な幾何学的対象が作られる。 凸多面体も様々な手順で得られる。

例えば, グラフの cut からは, cut polytope という \(0/1\)-polytope を作ることができる。

• cut polytope

また, associahedron の一般化として, graph associahedron というものもある。

• graph associahedron
• graph multiplihedron [DF08]

Permutahedron の一般化として, graphicahedron というものもある。

• graphicahedron

Araujo-Pardo, Del Río-Francos, López-Dudet, Oliveros, Schulte により, [Ara+10] で導入された。 単純グラフが与えられたときに, 辺をその両端の頂点の互換とみなすことにより, 頂点集合の対称群の生成元が得られる。その Cayley graph から作られる 抽象多面体である。 幾何学的な多面体ではないが, 興味深い構成である。

グラフの辺に長さが指定されているとき, 最短の道の長さを距離として, 頂点の間に距離を定めることができる。有限グラフからは, 有限距離空間ができるので, fundamental polytope やその polar dual である Lipschitz polytope という多面体が定義される。

• fundamental polytope

その特別な場合として symmetric edge polytope と呼ばれるものがある。 とても自然な構成だと思うが, 調べられるようになったのはつい最近のようで, Matsui らの [Mat+11] で導入されたもののようである。Chen と Korchevskaia の [CK] では, 同じものが adjacency polytope と呼ばれている。その quiver 版は directed edge polytope と呼ばれるものである。

• symmetric edge polytope あるいは adjacency polytope
• directed edge polytope

グラフ \(G\) の symmetric edge polytope は, \(G\) の辺を二重化してできる quiver の directed edge polytope なので, directed edge polytope の方が基本的であり, また quiver \(Q\) の directed edge polytope の面は, \(Q\) の subquiver の directed edge polytope で実現できる。 その facet を与える subquiver の特徴付けは, [NTT24] にある。

他にも次のようなものがある。

• edge polytope [OH00]
• matching polytope [Liu12; Esp+11]
• subgraph statistics から作られる polytope [EN11]
• hypergraphic polytope [BBM19]
• flow polytope [GS78]
• Postnikov の root polytope [Pos09]
• stable set polytope または vertex packing polytope [Ali+]
• graphical zonotope [Sta07]
• Eulerian subgraph polytope [BG86; RM]
• metric polytope [DD20]
• spanning trees polytope [Cha22]
• bond polytope [CJN]
• total matching polytope [Fer]

Edge polytope や flow polytope や root polytope は, \(\R ^{n}\) の標準的な正規直交基底 \(\{\bm {e}_{1},\ldots ,\bm {e}_{n}\}\) を用いて \(\pm \bm {e}_{i}\) や \(\bm {e}_{i}\pm \bm {e}_{j}\) の内いくつかの点の convex hull として定義されるが, Rietsch と Williams は [RW] そのような多面体を root polytope と呼んで調べている。

ただ, 既に root polytope という名前は, Cho [Cho99] や Cellini ら [CM15] のように, root 系 から作られる多面体に用いられているし, Postnikov [Pos09] は別の意味で用いている。 更に Rietsch と Williams が新しい “root polytope” を導入してしまったのは, 困ったことである。

References

[Ali+]

Farid Aliniaeifard, Carolina Benedetti, Nantel Bergeron, Shu Xiao Li, and Franco Saliola. Stable set polytopes and their 1-skeleta. arXiv: 1804.00360.

[Ara+10]

Gabriela Araujo-Pardo, Maria Del Río-Francos, Mariana López-Dudet, Deborah Oliveros, and Egon Schulte. “The graphicahedron”. In: European J. Combin. 31.7 (2010), pp. 1868–1879. arXiv: 0910.3908. url: http://dx.doi.org/10.1016/j.ejc.2010.03.004.

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

[Cho99]

Soojin Cho. “Polytopes of roots of type \(A_n\)”. In: Bull. Austral. Math. Soc. 59.3 (1999), pp. 391–402. url: https://doi.org/10.1017/S0004972700033062.

[CJN]

Markus Chimani, Martina Juhnke-Kubitzke, and Alexander Nover. On the Bond Polytope. arXiv: 2012.06288.

[CK]

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

[CM15]

Paola Cellini and Mario Marietti. “Root polytopes and Borel subalgebras”. In: Int. Math. Res. Not. IMRN 12 (2015), pp. 4392–4420. arXiv: 1203.0756. url: https://doi.org/10.1093/imrn/rnu070.

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

[DF08]

Satyan Devadoss and Stefan Forcey. “Marked tubes and the graph multiplihedron”. In: Algebr. Geom. Topol. 8.4 (2008), pp. 2081–2108. arXiv: 0807.4159. url: http://dx.doi.org/10.2140/agt.2008.8.2081.

[EN11]

Alexander Engström and Patrik Norén. “Polytopes from subgraph statistics”. In: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011). Discrete Math. Theor. Comput. Sci. Proc., AO. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011, pp. 305–316. arXiv: 1011.3552.

[Esp+11]

Louis Esperet, František Kardoš, Andrew D. King, Daniel Král, and Serguei Norine. “Exponentially many perfect matchings in cubic graphs”. In: Adv. Math. 227.4 (2011), pp. 1646–1664. arXiv: 1012.2878. url: https://doi.org/10.1016/j.aim.2011.03.015.

[Fer]

Luca Ferrarini. Facets of the Total Matching Polytope for bipartite graphs. arXiv: 2111.15528.

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

[Liu12]

Ricky Ini Liu. “Matching polytopes and Specht modules”. In: Trans. Amer. Math. Soc. 364.2 (2012), pp. 1089–1107. arXiv: 0910.0523. url: https://doi.org/10.1090/S0002-9947-2011-05516-9.

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

[NTT24]

Yasuhide Numata, Yusuke Takahashi, and Dai Tamaki. “Faces of directed edge polytopes”. In: Australas. J. Combin. 88 (2024), pp. 77–96. arXiv: 2203.14521.

[OH00]

Hidefumi Ohsugi and Takayuki Hibi. “Compressed polytopes, initial ideals and complete multipartite graphs”. In: Illinois J. Math. 44.2 (2000), pp. 391–406. url: http://projecteuclid.org/euclid.ijm/1255984847.

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

[RM]

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

[RW]

Konstanze Rietsch and Lauren Williams. Root polytopes, flow polytopes, and order polytopes. arXiv: 2406.15803.

[Sta07]

Richard P. Stanley. “An introduction to hyperplane arrangements”. In: Geometric combinatorics. Vol. 13. IAS/Park City Math. Ser. Amer. Math. Soc., Providence, RI, 2007, pp. 389–496. url: https://doi.org/10.1090/pcms/013/08.