Embedding products of graphs into Euclidean spaces

Mikhail Skopenkov

Fundamenta Mathematicae, Tome 177 (2003), p. 191-198 / Harvested from The Polish Digital Mathematics Library

Résumé

For any collection of graphs $G ₁, . . ., G_{N}$ we find the minimal dimension d such that the product $G ₁ \times . . . \times G_{N}$ is embeddable into $ℝ^{d}$ (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and $(K_{3, 3}) ⁿ$ are not embeddable into $ℝ^{2 n}$ , where K₅ and $K_{3, 3}$ are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding $L k O \to S^{2 n - 1}$ , where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.

Publié le : 2003-01-01

Zbl 1051.57032

EUDML-ID : urn:eudml:doc:283348

@article{bwmeta1.element.bwnjournal-article-doi-10_4064-fm179-3-1,
     author = {Mikhail Skopenkov},
     title = {Embedding products of graphs into Euclidean spaces},
     journal = {Fundamenta Mathematicae},
     volume = {177},
     year = {2003},
     pages = {191-198},
     zbl = {1051.57032},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm179-3-1}
}

Mikhail Skopenkov. Embedding products of graphs into Euclidean spaces. Fundamenta Mathematicae, Tome 177 (2003) pp. 191-198. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm179-3-1/