Publishing house / Journals and Serials / Fundamenta Mathematicae / All issues

Abstract

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.