Embedding products of graphs into Euclidean spaces

Tom 179 / 2003

Mikhail Skopenkov Fundamenta Mathematicae 179 (2003), 191-198 MSC: 57Q35, 57Q45. DOI: 10.4064/fm179-3-1


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.


  • Mikhail SkopenkovDepartment of Differential Geometry
    Faculty of Mechanics and Mathematics
    Moscow State University
    Moscow, 119992, Russia

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek