グラフの埋め込み

グラフを\(1\)次元 CW複体とみなすと, 幾何学的な対象として調べることができる。 例えば, より高次元の空間への埋め込みを考えることができる。

まず, 結び目の類似 (一般化) として, \(\R ^3\) や \(S^3\) へのグラフの埋め込みが考えられている。 Flapan らの [Fla02; Fla+06; FMN08; FH09] などがある。Huh と Lee の [HL15] で挙げられている文献も見るとよい。 この手のグラフの埋め込みについては, 当然ながら, 結び目に関して知られていることをグラフに一般化しようという研究が多い。

• total curvature に関する結果のグラフへの一般化 (Gulliver と Yamada の [GY12])
• Papakyriakopoulos の結果 [Pap57] の平面グラフへの一般化 (Scharlemann と Thompson の [ST91])

\(S^{3}\) に埋め込まれたグラフ \(\Gamma \) に対し, \(\Gamma \) を保つ \(S^{3}\) の同相写像の成す群を \(\Gamma \) の topological symmetry group と呼ぶ。 Simon により [Sim86] で導入されたもののようである。 やはり Flapan ら [CFO11; FMN11; FT13; CF14; FL14] が調べている。

• topological symmetry group

結び目の空間が考えられることから, グラフの 埋め込みの空間を考えるのも自然である。 実際, Galatius の [Gal11] などで使われている。

また, グラフの埋め込みと結び目の関係を調べることも行なわれている。 例えば, Abrams, Mellor, Trott の [AMT13] では, complete multipartite graph の \(S^3\) への埋め込みの中の link や knot の数が調べられている。

多様体への graph の埋め込みについては, intrinsically linked かどうかという問題がある。つまり, あるグラフ \(G\) の \(3\)次元多様体 \(M\) へのどんな埋め込みをとっても, \(G\) の cycle で nontrivial knot になっているものがあるのはどんな場合か, という問題である。 \(M\) が Euclid 空間の場合は, Conway と Gordon の [CG83] や Sachs の [Sac83; Sac84] などで調べられ始めたのだろうか。Conway と Gordon は \(K_7\) が intrinsically knotted であることを示している。Link の場合は, Robertson と Seymour と Thomas が [RST95] で考えている。 Goldberg と Mattman と Naimi [GMN] は, Euclid 空間の場合に数多くの intrinsically knotted graph を見付けている。 \(M\) が射影空間の場合は, Foisy らが [Bus+09] で考えている。

Euclid 空間に埋め込まれたグラフに対しては, 辺が真っ直ぐになるような埋め込みを考えたくなる。 そのようなものを (bar-joint) framework と言ったりする。

• bar-joint framework

Gromov と Guth [GG12] は, グラフの \(\R ^3\) への埋め込みの “geometric complexity” に関する Kolmogorov と Barzdin の60年代の結果 [Kol93] の高次元への一般化を考えている。

曲面上のグラフも重要である。

• 曲面上の graph や quiver

References

[AMT13]

Loren Abrams, Blake Mellor, and Lowell Trott. “Counting links and knots in complete graphs”. In: Tokyo J. Math. 36.2 (2013), pp. 429–458. arXiv: 1008.1085. url: https://doi.org/10.3836/tjm/1391177980.

[Bus+09]

Jason Bustamante et al. “Intrinsically linked graphs in projective space”. In: Algebr. Geom. Topol. 9.3 (2009), pp. 1255–1274. arXiv: 0809.0454. url: https://doi.org/10.2140/agt.2009.9.1255.

[CF14]

Dwayne Chambers and Erica Flapan. “Topological symmetry groups of small complete graphs”. In: Symmetry 6.2 (2014), pp. 189–209. arXiv: 1212.5964. url: https://doi.org/10.3390/sym6020189.

[CFO11]

Dwayne Chambers, Erica Flapan, and John D. O’Brien. “Topological symmetry groups of \(K_{4r+3}\)”. In: Discrete Contin. Dyn. Syst. Ser. S 4.6 (2011), pp. 1401–1411. arXiv: 0911.2794. url: https://doi.org/10.3934/dcdss.2011.4.1401.

[CG83]

J. H. Conway and C. McA. Gordon. “Knots and links in spatial graphs”. In: J. Graph Theory 7.4 (1983), pp. 445–453. url: http://dx.doi.org/10.1002/jgt.3190070410.

[FH09]

Erica Flapan and Hugh Howards. “Every graph has an embedding in \(S^3\) containing no non-hyperbolic knot”. In: Proc. Amer. Math. Soc. 137.12 (2009), pp. 4275–4285. arXiv: 0906.2229. url: https://doi.org/10.1090/S0002-9939-09-09972-9.

[FL14]

Erica Flapan and Emille Davie Lawrence. “Topological symmetry groups of Möbius ladders”. In: J. Knot Theory Ramifications 23.14 (2014), pp. 1450077, 13. arXiv: 1306.5483. url: https://doi.org/10.1142/S0218216514500771.

[Fla+06]

Erica Flapan, Hugh Howards, Don Lawrence, and Blake Mellor. “Intrinsic linking and knotting of graphs in arbitrary 3-manifolds”. In: Algebr. Geom. Topol. 6 (2006), pp. 1025–1035. arXiv: math/0508004. url: https://doi.org/10.2140/agt.2006.6.1025.

[Fla02]

Erica Flapan. “Intrinsic knotting and linking of complete graphs”. In: Algebr. Geom. Topol. 2 (2002), pp. 371–380. arXiv: math/0205231. url: https://doi.org/10.2140/agt.2002.2.371.

[FMN08]

Erica Flapan, Blake Mellor, and Ramin Naimi. “Intrinsic linking and knotting are arbitrarily complex”. In: Fund. Math. 201.2 (2008), pp. 131–148. arXiv: math/0610501. url: https://doi.org/10.4064/fm201-2-3.

[FMN11]

Erica Flapan, Blake Mellor, and Ramin Naimi. “Complete graphs whose topological symmetry groups are polyhedral”. In: Algebr. Geom. Topol. 11.3 (2011), pp. 1405–1433. arXiv: 1008.1095. url: https://doi.org/10.2140/agt.2011.11.1405.

[FT13]

Erica Flapan and Harry Tamvakis. “Topological symmetry groups of graphs in \(3\)-manifolds”. In: Proc. Amer. Math. Soc. 141.4 (2013), pp. 1423–1436. arXiv: 1108.2880. url: https://doi.org/10.1090/S0002-9939-2012-11405-4.

[Gal11]

Søren Galatius. “Stable homology of automorphism groups of free groups”. In: Ann. of Math. (2) 173.2 (2011), pp. 705–768. arXiv: math/0610216. url: http://dx.doi.org/10.4007/annals.2011.173.2.3.

[GG12]

Misha Gromov and Larry Guth. “Generalizations of the Kolmogorov-Barzdin embedding estimates”. In: Duke Math. J. 161.13 (2012), pp. 2549–2603. arXiv: 1103.3423. url: https://doi.org/10.1215/00127094-1812840.

[GMN]

Noam Goldberg, Thomas W. Mattman, and Ramin Naimi. Many, many more intrinsically knotted graphs. arXiv: 1109.1632.

[GY12]

Robert Gulliver and Sumio Yamada. “Total curvature of graphs after Milnor and Euler”. In: Pacific J. Math. 256.2 (2012), pp. 317–357. arXiv: 1101.2305. url: https://doi.org/10.2140/pjm.2012.256.317.

[HL15]

Youngsik Huh and Jung Hoon Lee. “Linearly embedded graphs in 3-space with homotopically free exteriors”. In: Algebr. Geom. Topol. 15.2 (2015), pp. 1161–1173. arXiv: 1409.6796. url: https://doi.org/10.2140/agt.2015.15.1161.

[Kol93]

A. N. Kolmogorov. Selected works of A. N. Kolmogorov. Vol. III. Vol. 27. Mathematics and its Applications (Soviet Series). Information theory and the theory of algorithms, With a biography of Kolmogorov by N. N. Bogolyubov, B. V. Gnedenko and S. L. Sobolev, With commentaries by R. L. Dobrushin, A. Kh. Shen\('\), V. M. Tikhomirov, Ya. M. Barzdin, Ya. G. Sinaı̆, V. A. Uspenski [V. A. Uspenskiı̆] and A. L. Semyonov, Edited by A. N. Shiryayev [A. N. Shiryaev], Translated from the 1987 Russian original by A. B. Sossinsky [A. B. Sosinskiı̆]. Dordrecht: Kluwer Academic Publishers Group, 1993, pp. xxvi+275. isbn: 90-277-2798-8.

[Pap57]

C. D. Papakyriakopoulos. “On Dehn’s lemma and the asphericity of knots”. In: Ann. of Math. (2) 66 (1957), pp. 1–26. url: https://doi.org/10.2307/1970113.

[RST95]

Neil Robertson, Paul Seymour, and Robin Thomas. “Sachs’ linkless embedding conjecture”. In: J. Combin. Theory Ser. B 64.2 (1995), pp. 185–227. url: http://dx.doi.org/10.1006/jctb.1995.1032.

[Sac83]

Horst Sachs. “On a spatial analogue of Kuratowski’s theorem on planar graphs—an open problem”. In: Graph theory (Łagów, 1981). Vol. 1018. Lecture Notes in Math. Berlin: Springer, 1983, pp. 230–241.

[Sac84]

H. Sachs. “On spatial representations of finite graphs”. In: Finite and infinite sets, Vol. I, II (Eger, 1981). Vol. 37. Colloq. Math. Soc. János Bolyai. Amsterdam: North-Holland, 1984, pp. 649–662.

[Sim86]

Jonathan Simon. “Topological chirality of certain molecules”. In: Topology 25.2 (1986), pp. 229–235. url: http://dx.doi.org/10.1016/0040-9383(86)90041-8.

[ST91]

Martin Scharlemann and Abigail Thompson. “Detecting unknotted graphs in \(3\)-space”. In: J. Differential Geom. 34.2 (1991), pp. 539–560. url: http://projecteuclid.org/euclid.jdg/1214447220.