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 の [Tim] にあるように, 同じ問題でも hypergraph の方がずっと困難である場合が多いことを知っておくべきだろう。 その中の一つとして, Timár は, perfect matching を見付ける algorithm を挙げている。

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

• hypergraph の chromatic polynomial
• interior polynomial と exterior polynomial

Fadnavis [Fad] は, hypergraph の chromatic polynomial に Sokal の graph の chromatic polynomial の零点に関する結果 [Sok] を一般化している。 Interior polynomial と exterior polynomial というのは, Kálmán [Kál13] が Tutte polynomial の specialization \(T(x,1)\) と \(T(1,y)\) の hypergraph版として導入したものである。

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の [Rus] である。

• oriented hypergraph

Elek と Szegedy [ES] は, 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+] など。

• determinantal hypergraph variety

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

• hypergraph の spectral theory

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

• vertex cover algebra

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

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

• quasi-tree

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

• hypergraph の combinatorial Hopf algebra

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.

[Bra]

Johann Brault-Baron. Hypergraph Acyclicity Revisited. arXiv: 1403. 7076.

[CD]

Joshua Cooper and Aaron Dutle. Spectra of Uniform Hypergraphs. arXiv: 1106.4856.

[Cla+]

Oliver Clarke, Kevin Grace, Fatemeh Mohammadi, and Harshit J Motwani. Matroid stratifications of hypergraph varieties, their realization spaces, and discrete conditional independence models. arXiv: 2103.16550.

[CN]

Alexandru Constantinescu and Le Dinh Nam. The standard graded property for vertex cover algebras of Quasi-Trees. 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.

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

[ES]

Gábor Elek and Balázs Szegedy. A measure-theoretic approach to the theory of dense hypergraphs. arXiv: 0810.4062.

[Fad]

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

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

[Rus]

Lucas J. Rusnak. Oriented Hypergraphs I: Introduction and Balance. arXiv: 1210.0943.

[Sok]

Alan D. Sokal. Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions. arXiv: cond-mat/ 9904146.

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

[Tim]

Adam Timar. Split hypergraphs. arXiv: 1109.6016.