グラフの一般化や変種

ものの繋がりを表すときには, グラフは最も基本的 (原始的) な道具である。より複雑な構造を表すときには, グラフに装飾をつけたりする。

Graph の formal linear combination は, graph complex を始めとして様々な構成に現われるが, そのようなものを quantum graph と呼んでいるのは, Lovász と Szegedy [LS] である。

  • quantum graph

トポロジーの視点からは, グラフを\(1\)次元の単体的複体 (胞体複体) とみなすのが普通かもしれない。 すると一般の単体的複体や胞体複体はグラフの一般化 (高次元化) とみなすことができる。

また, Kalai による この Math Overflow の質問 の答えの中には, 様々な平面グラフの一般化の例が集まっている。 その中には単体的複体より一般的な stratified space も入っている。

上記の Math Overflow の回答の一つとして, graph-like space という位相空間の class が挙げられている。Thomassen と Vella の [TV08] で導入されたものである。

  • graph-like space

Bowler らの [BCC] で, infinite matroid が graphic であることを特徴付けるのに使われている。

他にもグラフの高次元化は色々考えられている。

まず, 高次の圏の類似 (一般化) として, 高次の arrow を持つ quiverを考えることができる。 無限次のものは, Batanin と Street の [BS00] などにあるように, globular set である。 M’etayer の [Mét03] では, 途中までのものは, \(n\)-graph と呼ばれている。

まぎらわしい用語であるが, Kumjian と Pask [KP00] は, グラフの \(C^*\)-algebra の研究から, \(k\)-graph という概念を導入している。これはグラフというより rank 付きの small category を一般化したものである。

  • \(k\)-graph または higher-rank graph

Kumjian らは, [Kal+] で \(k\)-graph の topological realization を考えている。そして, [Kum+] でどのような空間が実現できるかについて調べている。また, [GK] では, コホモロジーを考えている。

単純グラフの辺は, 頂点集合 \(V\) の位数 \(2\) の部分集合と考えることができる。 より一般の部分集合を“辺”として考えると hypergraph ができる。

計算機科学者の Milner [Mil06] は, hypergraphtree を組み合わせた bigraph というものを考えている。それに関する本 [Mil09] も出版された。

  • bigraph

Bigraph とそれに関連したことの文献リストとしては, Bundgaard の管理しているものがある。

辺に広がりを持たせた ribbon graph というものもよく使われる。Penner らの [Pen+] で fat graph と呼ばれているものと同じもののようである。

その3次元版は, 数理物理に登場するようである。Tanasa の [Tan11] では, tensor graph と呼ばれていて, Bollobás-Riordan polynomial の一般化も考えられている。

Katsura の [Kat04; Kat06a; Kat06b; Kat] では topological graph という概念が定義されている。

  • topological graph

References

[BCC]

Nathan Bowler, Johannes Carmesin, and Robin Christian. Infinite graphic matroids Part I. arXiv: 1309.3735.

[BS00]

Michael Batanin and Ross Street. “The universal property of the multitude of trees”. In: J. Pure Appl. Algebra 154.1-3 (2000). Category theory and its applications (Montreal, QC, 1997), pp. 3–13. url: http://dx.doi.org/10.1016/S0022-4049(99)00184-X.

[GK]

Elizabeth Gillaspy and Alexander Kumjian. Cohomology for small categories: \(k\)-graphs and groupoids. arXiv: 1511.01073.

[Kal+]

S. Kaliszewski, Alex Kumjian, John Quigg, and Aidan Sims. Topological realizations and fundamental groups of higher-rank graphs. arXiv: 1205.2858.

[Kat]

Takeshi Katsura. A class of \(C^*\)-algebras generalizing both graph algebras and homeomorphism \(C^*\)-algebras IV, pure infiniteness. arXiv: math/0509343.

[Kat04]

Takeshi Katsura. “A class of \(C^*\)-algebras generalizing both graph algebras and homeomorphism \(C^*\)-algebras. I. Fundamental results”. In: Trans. Amer. Math. Soc. 356.11 (2004), 4287–4322 (electronic). arXiv: math/0207252. url: http://dx.doi.org/10.1090/S0002-9947-04-03636-0.

[Kat06a]

Takeshi Katsura. “A class of \(C^*\)-algebras generalizing both graph algebras and homeomorphism \(C^*\)-algebras. II. Examples”. In: Internat. J. Math. 17.7 (2006), pp. 791–833. arXiv: math/0405268. url: http://dx.doi.org/10.1142/S0129167X06003722.

[Kat06b]

Takeshi Katsura. “A class of \(C^*\)-algebras generalizing both graph algebras and homeomorphism \(C^*\)-algebras. III. Ideal structures”. In: Ergodic Theory Dynam. Systems 26.6 (2006), pp. 1805–1854. arXiv: math/0408190. url: http://dx.doi.org/10.1017/S0143385706000320.

[KP00]

Alex Kumjian and David Pask. “Higher rank graph \(C^*\)-algebras”. In: New York J. Math. 6 (2000), pp. 1–20. arXiv: math/0007029. url: http://nyjm.albany.edu:8000/j/2000/6_1.html.

[Kum+]

Alex Kumjian, David Pask, Aidan Sims, and Michael F. Whittaker. Topological spaces associated to higher-rank graphs. arXiv: 1310.6100.

[LS]

László Lovász and Balázs Szegedy. The graph theoretic moment problem. arXiv: 1010.5159.

[Mét03]

François Métayer. “Resolutions by polygraphs”. In: Theory Appl. Categ. 11 (2003), No. 7, 148–184.

[Mil06]

Robin Milner. “Pure bigraphs: structure and dynamics”. In: Inform. and Comput. 204.1 (2006), pp. 60–122. url: http://dx.doi.org/10.1016/j.ic.2005.07.003.

[Mil09]

Robin Milner. The Space and Motion of Communicating Agents. 1st ed. Cambridge University Press, Mar. 2009. isbn: 9780521490306.

[Pen+]

R. C. Penner, Michael Knudsen, Carsten Wiuf, and Joergen Ellegaard Andersen. Fatgraph Models of Proteins. arXiv: 0902.1025.

[Tan11]

Adrian Tanasa. “Generalization of the Bollobás-Riordan polynomial for tensor graphs”. In: J. Math. Phys. 52.7 (2011), pp. 073514, 17. arXiv: 1012.1798. url: https://doi.org/10.1063/1.3605312.

[TV08]

Carsten Thomassen and Antoine Vella. “Graph-like continua, augmenting arcs, and Menger’s theorem”. In: Combinatorica 28.5 (2008), pp. 595–623. url: http://dx.doi.org/10.1007/s00493-008-2342-9.