Linear finite models for locally finite transitive graphs

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For an infinite locally finite vertex-transitive graph $G$, let \[m_G(r)=\inf\{\operatorname{diam}(H):H\text{ is finite, connected, vertex-transitive and }B_H(v,r)\cong B_G(o,r)\},\] where the infimum of an empty set is $+\infty$ and balls are induced rooted graphs for unit-edge distance. Vertex-transitive means its automorphism group is transitive on vertices. The source calls $G$ $f(r)$-sofic when $m_G(r)=f(r)<\infty$ for every positive integer $r$.

Statement recorded in the supplied source.

If $m_G(r)<\infty$ for every $r$, must $m_G(r)\le cr$ for some constant $c=c(G)<\infty$? More uniformly, for each degree $d$, is there $c(d)<\infty$ such that every radius-$r$ rooted ball occurring in a finite $d$-regular vertex-transitive graph occurs in one of diameter at most $c(d)r$? Determine the smallest possible constants $c(d)$. [S2]

Short English statement

Are finite transitive models of a local neighborhood always available with diameter at most a constant times its radius?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 10000026 (AMR-099-0026). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Itai Benjamini, Coarse Geometry and Randomness, Saint-Flour lecture notes, version dated 30 October 2013; original author manuscript preserved in Arquivo.pt capture of 31 December 2020, Definition 5.5 and Open Problem 5.6, p. 40. https://arquivo.pt/noFrame/replay/20201231041548id_/http://www.wisdom.weizmann.ac.il/~itai/stflouraug24.pdf.