Graph Associahedra and Related Topics

重要な 凸多面体として associahedron, cyclohedron, permutohedron が あるが, これらは一般の グラフに対する graph associahedron と呼ばれる構成の, path, cycle, 完全グラフに対応する特別の場合と考えることができる。

Carr, Devadoss, Forcey の [CDF11] によると, graph associahedron は, De Concini と Procesi の subspace arrangement の complement の wonderful model の構成で最初に現われた。 その後, 様々なことと関係していることが分かってきている。上記の論文によると, wonderful model 以外に, 以下のことと関係がある:

• oriented matroid の Bergmann complex [ARW07]
• Seiberg-Witten Floer homology や Heegaard-Floer homology [Blo11]
• biological statistics [Mor+09]
• toric symplectic manifold [Del88; CP15]

Graph associahedron の具体的な構成としては, Devadoss の [Dev09] がある。Ma’u は [Mau] で stable quilted line with markings の moduli space の comppactification として実現できることを示している。

Carr, Devadoss, Forcey の [CDF11] は, 連結とは限らない loop や多重辺を持つ graph への一般化を構成している。その一般化により, 辺の deletion や contraction といった操作に対応する写像も構成できるようである。Devadoss と Forcey は [DF08] で multiplihedron の一般化を考えている。

• pseudograph associahedron
• graph multiplihedron

Devadoss, Hearth, Vipismakul [DHV11] は, 立方体から出発した graph cubeahedron という凸多面体の構成を導入している。

• graph cubeahedron

Devadoss, Forcey, Reisdorf, Showers [Dev+15] は, nestohedron を含むような一般化を考えている。

• nestohedron
• poset associahedron

Graph associahedron の性質は様々な面から調べられている。例えば, graph associahedron の \(1\)-skeleton のグラフとしての性質が Manneville と Pilaud [MP16] により調べられている。例えば, その直径が調べられているが, これは元のグラフの不変量としてはどのような情報を持っているのだろうか。

References

[ARW07]

Federico Ardila, Victor Reiner, and Lauren Williams. “Bergman complexes, Coxeter arrangements, and graph associahedra”. In: Sém. Lothar. Combin. 54A (2005/07), Art. B54Aj, 25 pp. (electronic). arXiv: math/0508240.

[Blo11]

Jonathan M. Bloom. “A link surgery spectral sequence in monopole Floer homology”. In: Adv. Math. 226.4 (2011), pp. 3216–3281. arXiv: 0909.0816. url: https://doi.org/10.1016/j.aim.2010.10.014.

[CDF11]

Michael Carr, Satyan L. Devadoss, and Stefan Forcey. “Pseudograph associahedra”. In: J. Combin. Theory Ser. A 118.7 (2011), pp. 2035–2055. arXiv: 1005.2551. url: http://dx.doi.org/10.1016/j.jcta.2011.04.004.

[CP15]

Suyoung Choi and Hanchul Park. “A new graph invariant arises in toric topology”. In: J. Math. Soc. Japan 67.2 (2015), pp. 699–720. arXiv: 1210.3776. url: https://doi.org/10.2969/jmsj/06720699.

[Del88]

Thomas Delzant. “Hamiltoniens périodiques et images convexes de l’application moment”. In: Bull. Soc. Math. France 116.3 (1988), pp. 315–339. url: http://www.numdam.org/item?id=BSMF_1988__116_3_315_0.

[Dev+15]

Satyan L. Devadoss, Stefan Forcey, Stephen Reisdorf, and Patrick Showers. “Convex polytopes from nested posets”. In: European J. Combin. 43 (2015), pp. 229–248. arXiv: 1306.4208. url: https://doi.org/10.1016/j.ejc.2014.08.018.

[Dev09]

Satyan L. Devadoss. “A realization of graph associahedra”. In: Discrete Math. 309.1 (2009), pp. 271–276. arXiv: math/0612530. url: http://dx.doi.org/10.1016/j.disc.2007.12.092.

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

[DHV11]

Satyan L. Devadoss, Timothy Heath, and Wasin Vipismakul. “Deformations of bordered surfaces and convex polytopes”. In: Notices Amer. Math. Soc. 58.4 (2011), pp. 530–541. arXiv: 1002.1676.

[Mau]

Sikimeti Ma’u. Quilted strips, graph associahedra, and \(A_{\infty }\) \(n\)-modules. arXiv: 1007.4620.

[Mor+09]

Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. “Convex rank tests and semigraphoids”. In: SIAM J. Discrete Math. 23.3 (2009), pp. 1117–1134. arXiv: math/0702564. url: https://doi.org/10.1137/080715822.

[MP16]

Thibault Manneville and Vincent Pilaud. “Graph properties of graph associahedra”. In: Sém. Lothar. Combin. 73 ([2014–2016]), Art. B73d, 31. arXiv: 1409.8114.