|
グラフは, 本によっては1次元の (有限) 単体的複体, あるいは胞体複体として定義されているが, 逆に胞体複体をグラフの高次元化とみなし,
グラフ理論の一般化を展開することもできる。
例えば, Catanzaro と Chernyak と Klein [CCK]は, グラフの代わりに胞体複体を用いた 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 が盛んに 調べられている。
代数的トポロジーとグラフとの関係としては, グラフから作られる 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.
-
[CCK]
-
Michael J. Catanzaro, Vladimir Y. Chernyak, and John R.
Klein. Kirchhoff’s theorems in higher dimensions and Reidemeister
torsion. arXiv: 1206.6783.
-
[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.
-
[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.
-
[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.
|
