Applications of Hypergraphs

Hypergraph は自然な graph の概念の拡張であるが, 最初に目にしたときに「何に使えるのか」と疑問に思う人は多いようである。 MathOverflow でも このような質問がある。

それによると, 生物学への応用もあるようである。 Klamt と Hausと Theisjno [KHT09] など。そこで挙げられているものには, Liu と Wu の [LW01] のように, computer science での応用が多いが。

群の空間への作用に関連したものでは, Radcliffe の [Rad] や Banakh らの [Ban+] などがある。

数論では, Wen-Ching Winnie Li らによる [FL96; LS96] や Sarveniazi の [Sar] などがある。

Timár の [Tim] では learning theory への応用として, Sloan と Turán の [ST97] が挙げられている。

References

[Ban+]

T. O. Banakh, O. Petrenko, I. V. Protasov, and S. Slobodianiuk. Kaleidoscopical Configurations in G-spaces. arXiv: 1001.0903.

[FL96]

Keqin Feng and Wen-Ch’ing Winnie Li. “Spectra of hypergraphs and applications”. In: J. Number Theory 60.1 (1996), pp. 1–22. url: http://dx.doi.org/10.1006/jnth.1996.0109.

[KHT09]

Steffen Klamt, Utz-Uwe Haus, and Fabian Theis. “Hypergraphs and cellular networks”. In: PLoS Comput. Biol. 5.5 (2009), e1000385, 6. url: http://dx.doi.org/10.1371/journal.pcbi.1000385.

[LS96]

Wen-Ch’ing Winnie Li and Patrick Solé. “Spectra of regular graphs and hypergraphs and orthogonal polynomials”. In: European J. Combin. 17.5 (1996), pp. 461–477. url: http://dx.doi.org/10.1006/eujc.1996.0040.

[LW01]

Duen-Ren Liu and Mei-Yu Wu. “A Hypergraph Based Approach to Declustering Problems”. In: Journal of Distributed and Parallel Databases 10.3 (2001), pp. 269–288.

[Rad]

David G. Radcliffe. Hyperreflection groups. arXiv: 1008.1084.

[Sar]

Alireza Sarveniazi. Ramunajan \((n_1,n_2,\ldots ,n_{d-1})\)-regular hypergraphs based on Bruhat-Tits Buildings of type \(\tilde{A}_{d-1}\). arXiv: math/0401181.

[ST97]

Robert H. Sloan and György Turán. “Learning from incomplete boundary queries using split graphs and hypergraphs (extended abstract)”. In: Computational learning theory (Jerusalem, 1997). Vol. 1208. Lecture Notes in Comput. Sci. Springer, Berlin, 1997, pp. 38–50. url: https://doi.org/10.1007/3-540-62685-9_5.

[Tim]

Adam Timar. Split hypergraphs. arXiv: 1109.6016.