Hypergraph から作られる単体的複体や胞体複体

グラフからは, 様々な方法で単体的複体が構成され, combinatorial algebraic topology の重要な研究対象になっている。当然 hypergraph に対する類似も考えられている。

まず, Kneser hypergraph の chromatic number について調べた, Alon と Frankl と Lovasz の [AFL86] がある。

Emtander [Emt09] は hypergraph の independence complex を定義している。

Shareshian と Wachs [SW09] は hypergraph matching complex を使って 対称群の Quillen complex のホモロジーを調べている。

Rundell [Run; Run12] によると, coloring complex の hypergraph 版は Breuer と Dall と Kubitzke [BDK12] と独立に Long と Rundell により導入されたらしい。Rundell は, cyclic coloring complex のホモロジーについて調べている。

Conant と Thistlethwaite は, [CT10] で hypergraph から theta complex という 単体的複体を構成し, そのホモトピー型を考えることを提唱している。その動機は, P/NP 問題らしい。

一方で, hypergraph は単体的複体の一般化とみなせることから, 与えられた hypergraph に「最も近い単体的複体」を考えることもできる。 例えば Parks と Lipscomb の Naval Surface Warfare Centerの technical report [PL91] にある。このことは, Bressan, Li, Ren, Wu の [Bre+19] で知った。この論文には, 他にも hypergraph のトポロジーについて簡単にまとめられている。

Bressan らは, この論文で hypergraph に対し embedded homology とその persistent 版を導入し調べている。

• embedded homology

グラフから cut polytope などの 多面体が作られるように, hypergraph からも多面体が作られ, 調べられている。例えば, De Concini と Procesi の subspace arrangement の wonderful model に現われる building set は, hypergraph と考えることができ, それに対し Feichtner と Sturmfels [FS05] と Postnikov [Pos09] により nestohedron という種類の凸多面体が構成されている。 Dosen と Petric の [DP11] で調べられている。 そこでは, 主に abstract polytope として構成され, hypergraph polytope と呼ばれているが。

• nestohedron あるいは hypergraph polytope

他には, Obradović の [Obr], Curien, Ivanović, Obradović の [COI19], Benedetti, Bergeron, Machacek の [BBM19], Curien, Delcroix-Oger, Obradović の [CDO] などがある。 Castro-Silva らの [Cas+] では independent-set polytope という多面体が登場する。

Hypergraph から作られる単体的複体でも多面体でもないが, Whitney の line graph の hypergraph への拡張が, Bermond と Heydemann と Sotteau の [BHS77] で導入されている。 単体的複体の場合が Olteanu の [Olt] で調べられている。

• line graph of hypergraph

References

[AFL86]

N. Alon, P. Frankl, and L. Lovász. “The chromatic number of Kneser hypergraphs”. In: Trans. Amer. Math. Soc. 298.1 (1986), pp. 359–370. url: http://dx.doi.org/10.2307/2000624.

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

[BDK12]

Felix Breuer, Aaron Dall, and Martina Kubitzke. “Hypergraph coloring complexes”. In: Discrete Math. 312.16 (2012), pp. 2407–2420. arXiv: 1104.0483. url: https://doi.org/10.1016/j.disc.2012.04.027.

[BHS77]

J. C. Bermond, M. C. Heydemann, and D. Sotteau. “Line graphs of hypergraphs. I”. In: Discrete Math. 18.3 (1977), pp. 235–241. url: https://doi.org/10.1016/0012-365X(77)90127-3.

[Bre+19]

Stephane Bressan, Jingyan Li, Shiquan Ren, and Jie Wu. “The embedded homology of hypergraphs and applications”. In: Asian J. Math. 23.3 (2019), pp. 479–500. arXiv: 1610.00890. url: https://doi.org/10.4310/AJM.2019.v23.n3.a6.

[Cas+]

Davi Castro-Silva, Fernando Mário de Oliveira Filho, Lucas Slot, and Frank Vallentin. A recursive theta body for hypergraphs. arXiv: 2206.03929.

[CDO]

Pierre-Louis Curien, Bérénice Delcroix-Oger, and Jovana Obradović. Tridendriform algebras on hypergraph polytopes. arXiv: 2201.05365.

[COI19]

Pierre-Louis Curien, Jovana Obradović, and Jelena Ivanović. “Syntactic aspects of hypergraph polytopes”. In: J. Homotopy Relat. Struct. 14.1 (2019), pp. 235–279. arXiv: 1708.02780. url: https://doi.org/10.1007/s40062-018-0211-9.

[CT10]

James Conant and Oliver Thistlethwaite. “Boolean formulae, hypergraphs and combinatorial topology”. In: Topology Appl. 157.16 (2010), pp. 2449–2461. arXiv: 0808.0739. url: http://dx.doi.org/10.1016/j.topol.2010.08.016.

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

[Emt09]

Eric Emtander. “Betti numbers of hypergraphs”. In: Comm. Algebra 37.5 (2009), pp. 1545–1571. arXiv: 0711.3368. url: http://dx.doi.org/10.1080/00927870802098158.

[FS05]

Eva Maria Feichtner and Bernd Sturmfels. “Matroid polytopes, nested sets and Bergman fans”. In: Port. Math. (N.S.) 62.4 (2005), pp. 437–468. arXiv: math/0411260.

[Obr]

Jovana Obradović. Combinatorial homotopy theory for operads. arXiv: 1906.06260.

[Olt]

Anda Olteanu. Line graphs of simplicial complexes. arXiv: 2206.13463.

[PL91]

A.D. Parks and S.L. Lipscomb. Homology and Hypergraph Acyclicity: A Combinatorial Invariant For Hypergraphs. Naval Surface Warfare Center, 1991, p. 9.

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

[Run]

Sarah Crown Rundell. The cyclic coloring complex of a complete k-uniform hypergraph. arXiv: 1105.4820.

[Run12]

Sarah Crown Rundell. “The coloring complex and cyclic coloring complex of a complete \(k\)-uniform hypergraph”. In: J. Combin. Theory Ser. A 119.5 (2012), pp. 1095–1109. arXiv: 1110.5007. url: https://doi.org/10.1016/j.jcta.2012.02.001.

[SW09]

John Shareshian and Michelle L. Wachs. “Top homology of hypergraph matching complexes, \(p\)-cycle complexes and Quillen complexes of symmetric groups”. In: J. Algebra 322.7 (2009), pp. 2253–2271. arXiv: 0808.3114. url: http://dx.doi.org/10.1016/j.jalgebra.2008.11.042.