Distance-two scaffolds have unbounded graph width

Research note, version 1, 24 September 2026.

Result

There is a one-state scaffolding automaton with degree two, distance two, and one working label whose reachable scaffolds contain every finite rectangular grid exactly. More precisely, for every r,c>=1, one input produces a scaffold whose labelled nodes, after forgetting edge directions and port names, induce the Cartesian grid P_r square P_c.

Since the n by n grid has treewidth n, the undirected treewidth and pathwidth of reachable scaffolds are unbounded. Therefore bounded update distance and bounded outdegree do not imply bounded graph width.

This is a structural calibration, not a language separation. The sole state may be accepting, so the machine can recognize the universal language while building these grids.

Construction

Let the input alphabet be {A,H,V,C}. Use ports 0 and 1, a single node label, one accepting state, and the following four update rows. Here lambda is the empty path from the old top.

The transition ignores the observed labels and control because both are constant. Its longest address has length two.

For r rows and c columns, read

$$w_{r,c}=A H^{c-1}(V C^{c-1})^{r-1}.$$

Interpret consecutive rows in alternating directions. The first row is built left to right, the second right to left, and so on. The machine does not store this orientation; it is a coordinate assignment used to describe the graph.

Port 0 points to the preceding cell in the row being built and is missing at the start of a row. Port 1 points to the cell immediately above and is missing in the first row. At a V symbol the old top already is that upper cell. At a C symbol, the previous new-row cell points by port 1 to its own upper cell. That old upper cell’s port 0 points to the next upper cell because the preceding row was built in the opposite direction. Thus path (1,0) reaches exactly the required vertical neighbor.

Induction over the snake order proves that every horizontal and vertical grid edge occurs and that no other edge occurs among labelled nodes. This proves the result.

Consequence for generalized pumping

The finite-interface pumping schema uses a tree-shaped derivation, and bounded treewidth is a natural first guess for extending it to persistent graphs. This construction rules out obtaining such a bound from scaffold degree and update distance alone. Even the smallest useful local mechanism can create arbitrarily wide grid memory.

The recurring interface must therefore describe how the fixed controller uses the graph, not merely the static topology of the entire archive. Bounded-width subclasses may still support graph-context pumping, but they are genuine restrictions on scaffold histories rather than consequences of locality.

Evidence and scope

The checker constructs every rectangle through 32 by 32 using the four rows above. It verifies 278,784 cells, 523,776 undirected edges, and 246,016 uses of the length-two descriptor against independently generated Cartesian grids. These finite checks corroborate the induction. They do not prove the standard grid-treewidth theorem, a language lower bound, or a pumping theorem.

The scaffold model and address semantics are from Loff, Moreira, and Reis, The computational power of parsing expression grammars, Definitions 10-13: https://arxiv.org/html/1902.08272v2#S4.SS1.

For a current overview stating that the n by n grid has treewidth n, see Daniel A. Spielman, Treewidth?, Notices of the AMS 72(2), 2025: https://www.ams.org/journals/notices/202502/rnoti-p172.pdf.

No priority claim is made without specialist review.

Version history

1. Initial construction, proof, bounded audit, and pumping consequence. No circulated paper or PDF was changed.