Embedding products of graphs into Euclidean spaces

Mikhail Skopenkov¹

¹ Department of Differential Geometry Faculty of Mechanics and Mathematics Moscow State University Moscow, 119992, Russia

Fundamenta Mathematicae, Tome 179 (2003) no. 3, pp. 191-198.

Résumé

For any collection of graphs $G_1,\dots,G_N$ we find the minimal dimension $d$ such that the product $G_1\times \dots\times G_N$ is embeddable into ${{\mathbb R}}^d$ (see Theorem 1 below). In particular, we prove that $(K_5)^n$ and $(K_{3,3})^n$ are not embeddable into ${{\mathbb R}}^{2n}$, where $K_5$ 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 $\mathop {\rm Lk}\nolimits O\to S^{2n-1}$, where $O$ is a vertex of $(K_5)^n$, has a pair of linked $(n-1)$-spheres.

Détail

DOI : 10.4064/fm179-3-1

Keywords: collection graphs dots minimal dimension product times dots times embeddable mathbb see theorem below particular prove embeddable mathbb where kuratowski graphs solution problem menger idea proof reduction problem so called ramsey link theory embedding mathop nolimits n where vertex has pair linked n spheres