The Ulam number of infinite graphs (Q1895817)

If \(X\) is the set of all integer points in the plane, two distinct sets \(A \subseteq X\) and \(B \subseteq X\) are called neighbours if, for some \((a,a') \in A\), \((b,b') \in B\), \(|a - b |\leq 1\), \(|a' - b' |\leq 1\). S. Ulam, in a problem published by \textit{Claude Berge} [Hypergraph seminar, Lect. Notes Math. 411 (1974; Zbl 0282.00007)], has conjectured that, for any partition of \(X\) whose classes are bounded by a given integer, there exists a class that has six neighbours. For any two graphs \(G\) and \(H\), a surjective map \(f : V(G) \to V(H)\) is a homomorphism of \(G\) onto \(H\) if \((x,y) \in E(G) \Rightarrow (f(x)\), \(f(y)) \in E(H)\) or \(f(x) = f(y)\); and \((x',y') \in E (H) \Rightarrow \exists x\), \(y \in V(G)\) such that \(f(x) = x'\), \(f(y) = y'\), and \((x,y) \in E(G)\); \(f\) is contractive if the subgraph \(G[f^{-1} (x)]\) induced by \(f^{-1} (x)\) is connected for every \(x \in V(H)\); \(f\) is uniformly bounded by \(m\) if \(|f^{-1} (x) |\leq m\) for all \(x\in V(H)\). The restricted Ulam number \(u_m (G)\) is \(\inf \{\Delta (H)\): \(H\) a homomorph of \(G\) uniformly bounded by \(m\}\); the Ulam number \(u(G)\) is \(\inf \{u_m (G) : m \geq 1\}\). The connected restricted and connected Ulam numbers \(U_m (G)\) and \(U(G)\) are defined analogously, with the additional constraint that \(H\) be connected. ``The \(\ldots\) Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6.'' Theorems 1-5 characterize graphs for which the Ulam number does not exceed 2. The connected Ulam number is determined for the integer and triangular grid graphs. A good drawing of \(G\) in \(\mathbb{R}^n\) is a representation such that there exists a function \(h : \mathbb{R}^+ \to \mathbb{N}\) such that any bounded subset of \(\mathbb{R}^n\) of diameter \(d\) contains at most \(h(d)\) vertices; and that the distance between two adjacent vertices is bounded. It is observed that an infinite graph \(G\) admits a good drawing in the plane only if \(u(G) \leq 6\); that \(G\) admits a good drawing with each edge appearing as a straight line segment parallel to one of the two coordinate axes only if \(u(G) \leq 4\); and that \(G\) admits a good drawing in a plane strip only if \(u(G) \leq 2\).