Hypergraph

グラフは辺と頂点から成る。 ループや多重辺を持たないグラフの辺は, 頂点の集合の位数\(2\)の部分集合として表されるが, より一般の位数の部分集合も許したものを hypergraph と呼ぶ。 本としては, Berge の [Ber73; Ber89] がある。

Grilliette [Gri] によると, hypergraph の category を調べたものとして, Dörfler と Waller の [DW80] がある。 Dörfler は, [Dör80] で hypergraph の covering などについても調べている。 Grilliette の [Gri] は, quiver の category と hypergraph の category を比較したものである。

• category of hypergraphs

Hypergraph は, かなり古くから様々な分野に登場しているようである。

• hypergraph の応用

Hypergraph について, まず考えるべきなのは, graph について分かっていることが, どれだけ hypergraph に一般化できるか, だろう。 ただし, Timár の [Tim08] にあるように, 同じ問題でも hypergraph の方がずっと困難である場合が多いことを知っておくべきだろう。 その中の一つとして, Timár は, perfect matching を見付ける algorithm を挙げている。

まずは, グラフに対し定義された概念や不変量を hypergraph への一般しようと考えるのは, 誰しも考えることだと思う。例えば, 不変量としては, グラフの多項式不変量の hypergraph 版がある。

• matching polynomial
• chromatic polynomial
• characteristic polynomial [CD12]
• Tutte polynomial

Wan らの [WWF] の冒頭にも書かれているが, hypergraph の多項式については, その零点の分布を調べることが, 主要な研究テーマの一つのようである。Wan らは matching polyonomial の零点の分布を調べている。

Fadnavis [Fad] は, hypergraph の chromatic polynomial に Sokal の graph の chromatic polynomial の零点に関する結果 [Sok01] を一般化している。

Hypergraph の Tutte polynomial は, Kálmán ら [BKP22] により導入された。 Kálmán は, [Kál13] では, Tutte polynomial の specialization \(T(x,1)\) と \(T(1,y)\) の hypergraph 版として, interior polynomial と exterior polyonomial を導入している。

• interior polynomial と exterior polynomial

Storm の [Sto06] で, graph の zeta 関数の hypergraph への拡張が定義されている。Emtander は, [Emt09] で hypergraph の Betti数について調べている。

グラフが acyclic (cycleを持たない) であることは, いくつかの一般化があるらしい。Brault-Baron の [Bra]では gamma acyclicity, beta acyclicity, alpha acyclicity などが挙げられている。

グラフに対し quiver (oriented graph) があるように, hypergraph の oriented version も考えられている。Reff と Rusnak の [RR12] や Rusnakの [Rus13] である。

• oriented hypergraph

Elek と Szegedy [ES12] は, hypergraph の列を 測度論的に扱うことを考えて, それによ り dense hypergraph の理論を構築している。それにより次の hypergraph に関する定理の別証を与えている。

• hypergraph regularity lemma
• hypergraph removal lemma

そのために, higher order Fourier analysis が有用なようであり, Szegedy は [Sze] でそのための代数的な理論の構築を始めている。

グラフからは, 既に 様々な種類の単体的複体が構成され, それらのホモトピー型を調べることにより chromatic number などに関する重要な結果も得られている。Hypergraph からも色んな単体的複体が作られて不思議ではない。 多面体を作ることもできる。

• hypergraph から作られた単体的複体や胞体複体

Hypergraph の頂点の色付けについては, グラフの vertex coloring の拡張以外にもいくつかのものが考えられている。例えば, Cheilaris と Smorodinsky の [CSS11] では, conflict-free coloring が考えられている。

Hypergraph の edge の色付けからは, braid arrangement に関係した subspace arrangement が構成 [MW12] される。これは, graph に対する graphic arrangement という hyperplane arrangement の構成の一般化である。

Hypergraph から作られる幾何学的構造としては, algebraic variety もある。 例えば, [Cla+23] など。

• determinantal hypergraph variety

Graph に対しては Laplacian などが定義され, その spectral theory が研究されているが, hypergraph に対しても, その類似を構成しようとう試みがある。 もちろん graph と行列との対応を一般化しなければならないので, 高次の線形代数が必要になる。例えば, Cooper と Dulte の試み [CD12] がある。

• hypergraph の spectral theory

Hypergraph の代数的な不変量としては, vertex cover algebra というものがある。

• vertex cover algebra

Herzog と Hibi と Trung の [HHT07] で導入された。 そこで定義されているのは, weighted simplicial complex に対するものであるが。

Quasi-tree という種類の hypergraph の場合に調べているのが, Constantinescu と Nam の [CN08] である。

• quasi-tree

Grujić, Stojadinović, Jojić の [GSJ16] では, hypergraph から作られた combinatorial Hopf algebra が調べられている。

• hypergraph の combinatorial Hopf algebra

Hypergraph の不変量としては, homology もある。 しかも, 様々な種類のものが定義されている。 例えば, Gasparovic らの [Gas+] では, 以下のようなものが挙げられている。

• closure homology
• restricted barycentric subdivision homology
• relative barycentric subdivision homology
• polar complex homology
• embedded homology
• path homology
• magnitude homology
• chromatic homology
• weighted nerve complex homology

他にも directed hypergraph に対しては, Diestel の [Die] で定義されているものもある。

References

[Ber73]

Claude Berge. Graphs and hypergraphs. Translated from the French by Edward Minieka, North-Holland Mathematical Library, Vol. 6. Amsterdam: North-Holland Publishing Co., 1973, pp. xiv+528.

[Ber89]

Claude Berge. Hypergraphs. Vol. 45. North-Holland Mathematical Library. Combinatorics of finite sets, Translated from the French. Amsterdam: North-Holland Publishing Co., 1989, pp. x+255. isbn: 0-444-87489-5.

[BKP22]

Olivier Bernardi, Tamás Kálmán, and Alexander Postnikov. “Universal Tutte polynomial”. In: Adv. Math. 402 (2022), Paper No. 108355, 74. arXiv: 2004.00683. url: https://doi.org/10.1016/j.aim.2022.108355.

[Bra]

Johann Brault-Baron. Hypergraph Acyclicity Revisited. arXiv: 1403.7076.

[CD12]

Joshua Cooper and Aaron Dutle. “Spectra of uniform hypergraphs”. In: Linear Algebra Appl. 436.9 (2012), pp. 3268–3292. arXiv: 1106.4856. url: https://doi.org/10.1016/j.laa.2011.11.018.

[Cla+23]

Oliver Clarke, Kevin Grace, Fatemeh Mohammadi, and Harshit J. Motwani. “Matroid stratifications of hypergraph varieties, their realization spaces, and discrete conditional independence models”. In: Int. Math. Res. Not. IMRN 22 (2023), pp. 18958–19019. arXiv: 2103.16550. url: https://doi.org/10.1093/imrn/rnac268.

[CN08]

Alexandru Constantinescu and Le-Dinh Nam. “The standard graded property for vertex cover algebras of quasi-trees”. In: Matematiche (Catania) 63.2 (2008), 173–183 (2009). arXiv: 0903.0545.

[CSS11]

Panagiotis Cheilaris, Shakhar Smorodinsky, and Marek Sulovský. “The potential to improve the choice: list conflict-free coloring for geometric hypergraphs”. In: Computational geometry (SCG’11). New York: ACM, 2011, pp. 424–432. arXiv: 1005.5520. url: http://dx.doi.org/10.1145/1998196.1998266.

[Die]

Reinhard Diestel. Homological aspects of oriented hypergraphs. arXiv: 2007.09125.

[Dör80]

W. Dörfler. “A homotopy theory for hypergraphs”. In: Glas. Mat. Ser. III 15(35).1 (1980), pp. 3–16.

[DW80]

W. Dörfler and D. A. Waller. “A category-theoretical approach to hypergraphs”. In: Arch. Math. (Basel) 34.2 (1980), pp. 185–192. url: https://doi.org/10.1007/BF01224952.

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

[ES12]

Gábor Elek and Balázs Szegedy. “A measure-theoretic approach to the theory of dense hypergraphs”. In: Adv. Math. 231.3-4 (2012), pp. 1731–1772. arXiv: 0810.4062. url: https://doi.org/10.1016/j.aim.2012.06.022.

[Fad]

Sukhada Fadnavis. On the roots of hypergraph chromatic polynomials. arXiv: 1509.05950.

[Gas+]

Ellen Gasparovic et al. A survey of simplicial, relative, and chain complex homology theories for hypergraphs. arXiv: 2409.18310.

[Gri]

Will Grilliette. A Functorial Link between Quivers and Hypergraphs. arXiv: 1608.00058.

[GSJ16]

Vladimir Grujić, Tanja Stojadinović, and Duško Jojić. “Generalized Dehn-Sommerville relations for hypergraphs”. In: Eur. J. Math. 2.2 (2016), pp. 459–473. arXiv: 1402.0421. url: https://doi.org/10.1007/s40879-015-0089-6.

[HHT07]

Jürgen Herzog, Takayuki Hibi, and Ngô Viêt Trung. “Symbolic powers of monomial ideals and vertex cover algebras”. In: Adv. Math. 210.1 (2007), pp. 304–322. arXiv: math/0512423. url: http://dx.doi.org/10.1016/j.aim.2006.06.007.

[Kál13]

Tamás Kálmán. “A version of Tutte’s polynomial for hypergraphs”. In: Adv. Math. 244 (2013), pp. 823–873. arXiv: 1103.1057. url: https://doi.org/10.1016/j.aim.2013.06.001.

[MW12]

Matthew S. Miller and Max Wakefield. “Edge colored hypergraphic arrangements”. In: Pure Appl. Math. Q. 8.3 (2012), pp. 757–779. arXiv: 0903.4221. url: https://doi.org/10.4310/PAMQ.2012.v8.n3.a9.

[RR12]

Nathan Reff and Lucas J. Rusnak. “An oriented hypergraphic approach to algebraic graph theory”. In: Linear Algebra Appl. 437.9 (2012), pp. 2262–2270. url: http://dx.doi.org/10.1016/j.laa.2012.06.011.

[Rus13]

Lucas J. Rusnak. “Oriented hypergraphs: introduction and balance”. In: Electron. J. Combin. 20.3 (2013), Paper 48, 29. arXiv: 1210.0943. url: https://doi.org/10.37236/2763.

[Sok01]

Alan D. Sokal. “Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions”. In: Combin. Probab. Comput. 10.1 (2001), pp. 41–77. arXiv: cond-mat/9904146. url: https://doi.org/10.1017/S0963548300004612.

[Sto06]

Christopher K. Storm. “The zeta function of a hypergraph”. In: Electron. J. Combin. 13.1 (2006), Research Paper 84, 26. arXiv: math/0608761. url: http://www.combinatorics.org/Volume_13/Abstracts/v13i1r84.html.

[Sze]

Balazs Szegedy. Higher order Fourier analysis as an algebraic theory I. arXiv: 0903.0897.

[Tim08]

Ádám Timár. “Split hypergraphs”. In: SIAM J. Discrete Math. 22.3 (2008), pp. 1155–1163. arXiv: 1109.6016. url: https://doi.org/10.1137/060675812.

[WWF]

Jiang-Chao Wan, Yi Wang, and Yi-zheng Fan. Distribution of zeros of matching polynomials of hypergraphs. arXiv: 2206.09558.