Your language?
Aug, 2018
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31

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 hypergraph

Hypergraph , かなり くから しているようである

Hypergraph について , まず えるべきなのは , graph について ていることが どれだけ hypergraph できるか , だろう ただし , Timár [ Tim08 ] にあるよう , でも hypergraph がず である いことを ておくべ きだろう その つとして , Timár , perfect matching ける algorithm げている

まずは , グラフ された 不変 hypergraph への しようと るのは , しも えることだと えば , 不変 としては グラフ 不変 hypergraph がある

  • hypergraph chromatic polynomial
  • interior polynomial exterior polynomial

Fadnavis [ Fad ] , hypergraph chromatic polynomial Sokal graph chromatic polynomial する [ Sok01 ] している 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 [ BB ] では 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 からも んな られて では ない

グラフ から cut polytope などの られるように , hypergraph からも られ 調 べられている えば , De Concini Procesi subspace arrangement wonderful model われる building set hypergraph えることができ , それに する nestohedron hypergraph する である Dosen Petric [ DP11 ] 調 べられている

Hypergraph 頂点 けについては , グラフ vertex coloring にもい くつかのものが えられている えば , Cheilaris Smorodinsky [ CSS11 ] では , conflict-free coloring えられている

Hypergraph edge けからは braid arrangement した subspace arrangement [ MW12 ] される これは graph する graphic arrangement いう hyperplane arrangement である

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

References

[BB]     Johann Brault-Baron. Hypergraph Acyclicity Revisited, arXiv:1403.7076 .

[Ber73]     Claude Berge. Graphs and hypergraphs . North-Holland Publishing Co., Amsterdam, 1973. Translated from the French by Edward Minieka, North-Holland Mathematical Library, Vol. 6.

[Ber89]     Claude Berge. Hypergraphs , volume 45 of North-Holland Mathematical Library . North-Holland Publishing Co., Amsterdam, 1989. Combinatorics of finite sets, Translated from the French.

[CD12]     Joshua Cooper and Aaron Dutle. Spectra of uniform hypergraphs. Linear Algebra Appl. , 436(9):3268–3292, 2012, arXiv:1106.4856 .

[CN08]     Alexandru Constantinescu and Le-Dinh Nam. The standard graded property for vertex cover algebras of quasi-trees. Matematiche (Catania) , 63(2):173–183 (2009), 2008, 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) , pages 424–432. ACM, New York, 2011, arXiv:1005.5520 .

[Dör80]     W. Dörfler. A homotopy theory for hypergraphs. Glas. Mat. Ser. III , 15(35)(1):3–16, 1980.

[DP11]     Kosta Došen and Zoran Petrić. Hypergraph polytopes. Topology Appl. , 158(12):1405–1444, 2011, arXiv:1010.5477 .

[DW80]     W. Dörfler and D. A. Waller. A category-theoretical approach to hypergraphs. Arch. Math. (Basel) , 34(2):185–192, 1980, https://doi.org/10.1007/BF01224952 .

[Emt09]     Eric Emtander. Betti numbers of hypergraphs. Comm. Algebra , 37(5):1545–1571, 2009, arXiv:0711.3368 .

[ES12]     Gábor Elek and Balázs Szegedy. A measure-theoretic approach to the theory of dense hypergraphs. Adv. Math. , 231(3-4):1731–1772, 2012, 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. Eur. J. Math. , 2(2):459–473, 2016, arXiv:1402.0421 .

[HHT07]     Jürgen Herzog, Takayuki Hibi, and Ngô Viêt Trung. Symbolic powers of monomial ideals and vertex cover algebras. Adv. Math. , 210(1):304–322, 2007, arXiv:math/0512423 .

[Kál13]     Tamás Kálmán. A version of Tutte’s polynomial for hypergraphs. Adv. Math. , 244:823–873, 2013, arXiv:1103.1057 .

[MW12]     Matthew S. Miller and Max Wakefield. Edge colored hypergraphic arrangements. Pure Appl. Math. Q. , 8(3):757–779, 2012, arXiv:0903.4221 .

[RR12]     Nathan Reff and Lucas J. Rusnak. An oriented hypergraphic approach to algebraic graph theory. Linear Algebra Appl. , 437(9):2262–2270, 2012, http://dx.doi.org/10.1016/j.laa.2012.06.011 .

[Rus13]     Lucas J. Rusnak. Oriented hypergraphs: introduction and balance. Electron. J. Combin. , 20(3):Paper 48, 29, 2013, arXiv:1210.0943 .

[Sok01]     Alan D. Sokal. Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combin. Probab. Comput. , 10(1):41–77, 2001, arXiv:cond-mat/9904146 .

[Sto06]     Christopher K. Storm. The zeta function of a hypergraph. Electron. J. Combin. , 13(1):Research Paper 84, 26 pp. (electronic), 2006, arXiv:math/0608761 .

[Sze]     Balazs Szegedy. Higher order Fourier analysis as an algebraic theory I, arXiv:0903.0897 .

[Tim08]     Ádám Timár. Split hypergraphs. SIAM J. Discrete Math. , 22(3):1155–1163, 2008, arXiv:1109.6016 .