The Ulam Number of Infinite Graphs

NEW

Problem: Reconstructed statement: let $C(\{k_i\},\{n_i\})$ be the comb with spine vertices $x_0,x_1,\dots$, a tooth of length $k_i$ attached at spine position $p_i$, where $p_i=n_i$ if the $n_i$’s denote attachment positions and $p_i=n_1+\cdots+n_i$ if they denote gaps. Thus edges are

The Ulam number $u(G)$ is the minimum, over partitions of $V(G)$ into uniformly cardinality-bounded parts, of the maximum degree of the quotient graph.

Result: The comb has Ulam number $2$ exactly for the following sequences.

There exist integers $A,D\ge1$, a sequence $a_m\in\mathbb Z$, and signs $\varepsilon_i\in\{\pm1\}$ such that

and the anchored intervals

have uniformly bounded overlap:

Proof sketch. A connected infinite graph has $u(G)=2$ iff it admits a map $F:V(G)\to\mathbb Z$ with uniformly bounded fibres and $|F(u)-F(v)|\le1$ on every edge. One direction comes from labelling the quotient path of a bounded partition; the other partitions by level sets of $F$. Since a connected infinite quotient cannot have maximum degree $0$ or $1$, this gives $u=2$.

For the comb, such an $F$ gives $a_m=F(x_m)$. Each tooth-label walk starts at $a_{p_i}$, has length $k_i$, and has at most $N$ vertices at any label, so it must extend at least $\lfloor k_i/(4N)\rfloor$ labels to one side. Choosing that side gives the intervals above with bounded overlap.

Conversely, given $A,D,a_m,\varepsilon_i$, define

Then adjacent vertices change label by at most $1$, and every fibre has size at most $D+AD$. Hence the level partition has quotient maximum degree at most $2$, so $u(C)=2$.

Citation: Definitions and the general Ulam-number framework are from K. B. Chilakamarri and N. Dean, “The Ulam number of infinite graphs,” Graphs and Combinatorics 11 (1995), 109–120, DOI: 10.1007/BF01929480.