Embedding products of graphs into Euclidean spaces

Volume 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

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image