グラフの埋め込み

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

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

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

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

また, グラフの埋め込みと結び目の関係を調べることも行なわれている。 例えば, Abrams, Mellor, Trott の [AMT] では, 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 らが [Foi+] で考えている。

Euclid 空間の中のグラフの問題としては, その rigidity を組み合せ論的に特徴付ける, というものがある。 Develin と Martin と Reiner の [DMR07] はその問題を matroid に一般化して考えようという試みである。 “Space of photos” という代数多様体が現れたりして面白そうである。

• matroid

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

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

• 曲面上の graph や quiver

References

[AMT]

Loren Abrams, Blake Mellor, and Lowell Trott. Counting Links and Knots in Complete Graphs. arXiv: 1008.1085.

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

[DMR07]

Mike Develin, Jeremy L. Martin, and Victor Reiner. “Rigidity theory for matroids”. In: Comment. Math. Helv. 82.1 (2007), pp. 197–233. arXiv: math/0503050. url: http://dx.doi.org/10.4171/CMH/89.

[FH]

Erica Flapan and Hugh Howards. Every graph has an embedding in \(S^3\) containing no non-hyperbolic knot. arXiv: 0906.2229.

[Fla]

Erica Flapan. Intrinsic knotting and linking of complete graphs. arXiv: math/0205231.

[Fla+]

Erica Flapan, Hugh Howards, Don Lawrence, and Blake Mellor. Intrinsic linking and knotting of graphs in arbitrary 3-manifolds. arXiv: math/0508004.

[FMN]

Erica Flapan, Blake Mellor, and Ramin Naimi. Intrinsic linking and knotting are arbitrarily complex. arXiv: math/0610501.

[Foi+]

Joel Foisy et al. Intrinsically Linked Graphs in Projective Space. arXiv: 0809.0454.

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

[GG]

Misha Gromov and Larry Guth. Generalizations of the Kolmogorov-Barzdin embedding estimates. arXiv: 1103.3423.

[GMN]

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

[GY]

Robert Gulliver and Sumio Yamada. Total Curvature of Graphs after Milnor and Euler. arXiv: 1101.2305.

[HL]

Youngsik Huh and Jung Hoon Lee. Linearly embedded graphs in 3-space with homotopically free exteriors. arXiv: 1409.6796.

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

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