グラフの一般化や変種

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

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

辺に向きが付いたグラフ, つまり有向グラフや quiver と呼ばれるものも, 辺に向きというラベルが付いたグラフである。

• quiver

一部の辺にだけ向きを付いたものを考えてもよい。そのようなものは, [HLM] では mixed graph と呼ばれている。

• mixed graph

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

ただ, 現在一般的に quantum graph と呼ばれているものは, 頂点や辺の集合を quantum set, つまり有限次元 \(C^{*}\)-algebra にしたもののようである。Gromada の [Gro22] を見るとよい。 Daws [Daw] によると, 最初の定義は quantum commnication channel の研究 [DSW13] で登場し, Weaver ら [KW12; Wea12; Wea21] により von Neumann algebra を用いて reformulate されたようである。

• quantum graph

他にも Frobenius algebra を用いたもの [MRV18; MRV19] もある。 Kuchment [Kuc04; Kuc05; FKW07] による self-adjoint differential operator を持つ metric graph としての 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] でどのような空間が実現できるかについて調べている。また, [GK18] では, コホモロジーを考えている。

単純グラフの辺は, 頂点集合 \(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.

[Daw]

Matthew Daws. Quantum graphs: different perspectives, homomorphisms and quantum automorphisms. arXiv: 2203.08716.

[DSW13]

Runyao Duan, Simone Severini, and Andreas Winter. “Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number”. In: IEEE Trans. Inform. Theory 59.2 (2013), pp. 1164–1174. arXiv: 1002 . 2514. url: https://doi.org/10.1109/TIT.2012.2221677.

[FKW07]

S. A. Fulling, P. Kuchment, and J. H. Wilson. “Index theorems for quantum graphs”. In: J. Phys. A 40.47 (2007), pp. 14165–14180. arXiv: 0708.3456. url: https://doi.org/10.1088/1751-8113/40/47/009.

[GK18]

Elizabeth Gillaspy and Alexander Kumjian. “Cohomology for small categories: \(k\)-graphs and groupoids”. In: Banach J. Math. Anal. 12.3 (2018), pp. 572–599. arXiv: 1511 . 01073. url: https://doi.org/10.1215/17358787-2017-0041.

[Gro22]

Daniel Gromada. “Some examples of quantum graphs”. In: Lett. Math. Phys. 112.6 (2022), Paper No. 122, 49. arXiv: 2109.13618. url: https://doi.org/10.1007/s11005-022-01603-5.

[HLM]

Xueyi Huang, Lu Lu, and Katja Mönius. Splitting fields of mixed Cayley graphs over abelian groups. arXiv: 2202.00987.

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

[Kuc04]

Peter Kuchment. “Quantum graphs. I. Some basic structures”. In: Waves Random Media 14.1 (2004). Special section on quantum graphs, S107–S128. url: http://dx.doi.org/10.1088/0959-7174/14/1/014.

[Kuc05]

Peter Kuchment. “Quantum graphs. II. Some spectral properties of quantum and combinatorial graphs”. In: J. Phys. A 38.22 (2005), pp. 4887–4900. arXiv: math - ph / 0411003. url: https://doi.org/10.1088/0305-4470/38/22/013.

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

[KW12]

Greg Kuperberg and Nik Weaver. “A von Neumann algebra approach to quantum metrics”. In: Mem. Amer. Math. Soc. 215.1010 (2012), pp. v, 1–80. arXiv: 1005 . 0353. url: https://doi.org/10.1090/S0065-9266-2011-00637-4.

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

[MRV18]

Benjamin Musto, David Reutter, and Dominic Verdon. “A compositional approach to quantum functions”. In: J. Math. Phys. 59.8 (2018), pp. 081706, 42. arXiv: 1711 . 07945. url: https://doi.org/10.1063/1.5020566.

[MRV19]

Benjamin Musto, David Reutter, and Dominic Verdon. “The Morita theory of quantum graph isomorphisms”. In: Comm. Math. Phys. 365.2 (2019), pp. 797–845. arXiv: 1801.09705. url: https://doi.org/10.1007/s00220-018-3225-6.

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