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

グラフは, 本によっては1次元の (有限) 単体的複体, あるいは 胞体複体として定義されているが, 逆に胞体複体をグラフの高次元化とみなし, グラフ理論の一般化を展開することもできる。

例えば, Catanzaro と Chernyak と Klein [CCK15]は, グラフの代わりに胞体複体を用いた Kirchhoff の network theorem の高次元版を考えている。 Cappell と Miller [CM] は, その一般化や Trent の定理の一般化を考えている。 この Cappell と Miller の論文の Introduction の最後に, グラフ理論の胞体複体への一般化に関する文献のリストがある。

このように, 単体的複体をグラフの高次元化とみなすことを考え始めたのは誰なのだろうか。 Spanning tree の類似を調べたものとして, Kalai の [Kal83] があるが, これが最も古いものだろうか。Spanning tree の類似を調べたものとしては, Duval と Klivans と Martin の [DKM09; DKM11a] や Lyons の [Lyo09] もある。

最近では, Erdős と Rényi の random graph [ER59; ER60] の一般化として random simplicial complex が盛んに 調べられている。

• random simplicial complex

Tree の一般化として考えられる simplicial complex の class として stacked simplicial complex というものがある。Fløystad ら [FO23; Flø24] により調べられている。 Dao と Schweig の [DS19] のように facet constructible complex と呼ばれることもあるようである。

• stacked simplicial complex

代数的トポロジーとグラフとの関係としては, グラフから作られる simplicial complex が重要であるが, simplicial complex に一般化されているものもある。例えば, Hom complex の simplicial complex の一般化は Zivaljevic [Živ09] により考えられている。

グラフ理論では minor の概念が重要であるが, それも simplicial complex に一般化されている。Nevo の [Nev07; Nev] など。 Dey, Hirani, Krishnamoorthy, Smith の [Dey+]によると, 関連した simplicial complex の edge contraction は, 応用トポロジーに使えるようである。

Chordal graph とは, 長さ4以上の cycle が cycle の辺以外の辺で結ばれる頂点を持つ graph であるが, その simplicial complex 版が Adiprasito と Nevo と Samper の [ANS16] で考えられている。

Elek は, グラフの distributional limit [BS] の類似として単体的複体の列の収束を [Ele10] で定義している。

Duval と Klivans と Martin は [DKM11b; DKM15] で graph の critical group の単体的複体や胞体複体への一般化を定義し調べている。

グラフの不変量の simplicial complex や cell complex への一般化も色々定義されている。 Beckと Breuerと Godkin と Martin の [Bec+14] では, chromatic polynomial や flow polynomial などの一般化が任意のCW複体に対し定義されている。

グラフの色付け (vertex coloring) も自然に単体的複体に一般化される。 単体的複体の色付けに関する命題として Sperner’s lemma [Spe28] がある。Musin [Mus] によると Brouwer fixed point theorem の離散版とみなすことができるらしい。

References

[ANS16]

Karim A. Adiprasito, Eran Nevo, and Jose A. Samper. “Higher chordality: from graphs to complexes”. In: Proc. Amer. Math. Soc. 144.8 (2016), pp. 3317–3329. arXiv: 1503.05620. url: https://doi.org/10.1090/proc/13002.

[Bec+14]

Matthias Beck, Felix Breuer, Logan Godkin, and Jeremy L. Martin. “Enumerating colorings, tensions and flows in cell complexes”. In: J. Combin. Theory Ser. A 122 (2014), pp. 82–106. arXiv: 1212.6539. url: https://doi.org/10.1016/j.jcta.2013.10.002.

[BS]

Itai Benjamini and Oded Schramm. Recurrence of Distributional Limits of Finite Planar Graphs. arXiv: math/0011019.

[CCK15]

Michael J. Catanzaro, Vladimir Y. Chernyak, and John R. Klein. “Kirchhoff’s theorems in higher dimensions and Reidemeister torsion”. In: Homology Homotopy Appl. 17.1 (2015), pp. 165–189. arXiv: 1206.6783. url: https://doi.org/10.4310/HHA.2015.v17.n1.a8.

[CM]

Sylvain E. Cappell and Edward Y. Miller. Enumerative Combinatorics of Simplicial and Cell Complexes: Kirchhoff and Trent Type Theorems. arXiv: 1506.03881.

[Dey+]

Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy, and Gavin Smith. Edge Contractions and Simplicial Homology. arXiv: 1304.0664.

[DKM09]

Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. “Simplicial matrix-tree theorems”. In: Trans. Amer. Math. Soc. 361.11 (2009), pp. 6073–6114. arXiv: 0802.2576. url: http://dx.doi.org/10.1090/S0002-9947-09-04898-3.

[DKM11a]

Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. “Cellular spanning trees and Laplacians of cubical complexes”. In: Adv. in Appl. Math. 46.1-4 (2011), pp. 247–274. arXiv: 0908.1956. url: http://dx.doi.org/10.1016/j.aam.2010.05.005.

[DKM11b]

Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. “Critical groups of simplicial complexes”. In: 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011). Discrete Math. Theor. Comput. Sci. Proc., AO. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011, pp. 269–280. arXiv: 1101.3981.

[DKM15]

Art M. Duval, Caroline J. Klivans, and Jeremy L. Martin. “Cuts and flows of cell complexes”. In: J. Algebraic Combin. 41.4 (2015), pp. 969–999. arXiv: 1206.6157. url: https://doi.org/10.1007/s10801-014-0561-2.

[DS19]

Hailong Dao and Jay Schweig. “The type defect of a simplicial complex”. In: J. Combin. Theory Ser. A 163 (2019), pp. 195–210. arXiv: 1704.01243. url: https://doi.org/10.1016/j.jcta.2018.11.015.

[Ele10]

Gábor Elek. “Betti numbers are testable”. In: Fete of combinatorics and computer science. Vol. 20. Bolyai Soc. Math. Stud. Budapest: János Bolyai Math. Soc., 2010, pp. 139–149. arXiv: 0907.5302.

[ER59]

P. Erdős and A. Rényi. “On random graphs. I”. In: Publ. Math. Debrecen 6 (1959), pp. 290–297.

[ER60]

P. Erdős and A. Rényi. “On the evolution of random graphs”. In: Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), pp. 17–61.

[Flø24]

Gunnar Fløystad. “Partitions of vertices and facets in trees and stacked simplicial complexes”. In: Graphs Combin. 40.4 (2024), Paper No. 79, 22. arXiv: 2207.04444. url: https://doi.org/10.1007/s00373-024-02804-6.

[FO23]

Gunnar Fløystad and Milo Orlich. “Triangulations of polygons and stacked simplicial complexes: separating their Stanley-Reisner ideals”. In: J. Algebraic Combin. 57.3 (2023), pp. 659–686. arXiv: 2108.06520. url: https://doi.org/10.1007/s10801-022-01174-7.

[Kal83]

Gil Kalai. “Enumeration of \(\Q \)-acyclic simplicial complexes”. In: Israel J. Math. 45.4 (1983), pp. 337–351. url: http://dx.doi.org/10.1007/BF02804017.

[Lyo09]

Russell Lyons. “Random complexes and \(l^2\)-Betti numbers”. In: J. Topol. Anal. 1.2 (2009), pp. 153–175. arXiv: 0811.2933. url: http://dx.doi.org/10.1142/S1793525309000072.

[Mus]

Oleg R Musin. Around Sperner’s lemma. arXiv: 1405.7513.

[Nev]

Eran Nevo. Algebraic Shifting and f-Vector Theory. arXiv: 0709.3265.

[Nev07]

Eran Nevo. “Higher minors and Van Kampen’s obstruction”. In: Math. Scand. 101.2 (2007), pp. 161–176. arXiv: math/0602531.

[Spe28]

E. Sperner. “Neuer beweis für die invarianz der dimensionszahl und des gebietes”. In: Abh. Math. Sem. Univ. Hamburg 6.1 (1928), pp. 265–272. url: https://doi.org/10.1007/BF02940617.

[Živ09]

Rade T. Živaljević. “Combinatorial groupoids, cubical complexes, and the Lovász conjecture”. In: Discrete Comput. Geom. 41.1 (2009), pp. 135–161. arXiv: math/0510204. url: http://dx.doi.org/10.1007/s00454-008-9062-1.