グラフの一般化や変種

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

• 辺や頂点にラベルの付いたグラフや quiver

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

ただ, 現在一般的に quantum graph と呼ばれているものは, 頂点や辺の集合を quantum set, つまり有限次元 \(C^{*}\)-algebra にしたもののようである。Gromada の [Gro] を見るとよい。 それによると, その意味の quantum graph は Weaver [Wea12; Wea21] により導入されたもののようである。

• quantum graph

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

• グラフの高次元化としての単体的複体や胞体複体

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

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

• graph-like space

Bowler らの [BCC; BCC18] で, infinite matroid が graphic であることを特徴付けるのに使われている。 この matroid という概念は, 重要なグラフの一般化であるが, グラフ以外の様々な組み合せ論的構造の抽象化にもなっている。

• matroid

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

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

• globular set

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

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

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

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

• hypergraph

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

• bigraph

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

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

• ribbon graph あるいは fat graph

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

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

• topological graph

References

[BCC]

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

[BCC18]

Nathan Bowler, Johannes Carmesin, and Robin Christian. “Infinite graphic matroids”. In: Combinatorica 38.2 (2018), pp. 305–339. url: https://doi.org/10.1007/s00493-016-3178-3.

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

[Gro]

Daniel Gromada. Some examples of quantum graphs. arXiv: 2109. 13618.

[Kal+16]

S. Kaliszewski, Alex Kumjian, John Quigg, and Aidan Sims. “Topological realizations and fundamental groups of higher-rank graphs”. In: Proc. Edinb. Math. Soc. (2) 59.1 (2016), pp. 143–168. arXiv: 1205.2858. url: https://doi.org/10.1017/S0013091515000061.

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

[Kat08]

Takeshi Katsura. “A class of \(C^*\)-algebras generalizing both graph algebras and homeomorphism \(C^*\)-algebras. IV. Pure infiniteness”. In: J. Funct. Anal. 254.5 (2008), pp. 1161–1187. arXiv: math/0509343. url: https://doi.org/10.1016/j.jfa.2007.11.014.

[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+16]

Alex Kumjian, David Pask, Aidan Sims, and Michael F. Whittaker. “Topological spaces associated to higher-rank graphs”. In: J. Combin. Theory Ser. A 143 (2016), pp. 19–41. arXiv: 1310.6100. url: https://doi.org/10.1016/j.jcta.2016.04.005.

[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+10]

R. C. Penner, Michael Knudsen, Carsten Wiuf, and Jørgen Ellegaard Andersen. “Fatgraph models of proteins”. In: Comm. Pure Appl. Math. 63.10 (2010), pp. 1249–1297. arXiv: 0902.1025. url: https://doi.org/10.1002/cpa.20340.

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

[Wea12]

Nik Weaver. “Quantum relations”. In: Mem. Amer. Math. Soc. 215.1010 (2012), pp. v–vi, 81–140. arXiv: 1005 . 0354. url: http://www.ams.org/books/memo/1010/.

[Wea21]

Nik Weaver. “Quantum graphs as quantum relations”. In: J. Geom. Anal. 31.9 (2021), pp. 9090–9112. arXiv: 1506.03892. url: https://doi.org/10.1007/s12220-020-00578-w.