Self-avoiding walks on cubic graphs and local transformations

Benjamin Grant, Zhongyang Li · 2026

Read Self-avoiding walks on cubic graphs and local transformations by Benjamin Grant, Zhongyang Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-12571.txt.

Introduction

Benjamin Grant and Zhongyang Li study self avoiding walks on cubic graphs. A self avoiding walk never visits the same vertex twice. Cubic graphs give each vertex degree three, and the graphs here are infinite and quasi transitive. The team apply local transformations that swap each vertex for a small gadget. Each gadget is finite, symmetric, and has three ports.

To each gadget they attach a two port generating function. That function counts walks that enter and exit the gadget through set ports. Generating functions turn counting problems into algebra that can be solved. Local swaps of this kind let one graph be reshaped into another. The work asks which walk counts survive such reshaping, a core question in combinatorics.

Catalog record

CREATORBenjamin Grant, Zhongyang Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-12571

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Self-avoiding walks on cubic graphs and local transformations Benjamin Grant, Zhongyang Li Abstract . We study self-avoiding walks (SAWs) on infinite quasi-transitive cubic graphs under local transformations that replace each degree- 3 3 vertex by a finite, symmetric three-port gadget. To each gadget we associate a two-port SAW generating function g ⁡ ( x ) g(x) , defined by counting SAWs that enter and exit the gadget through prescribed ports. Our first main result shows that, if G G is cubic and G 1 = ϕ ⁡ ( G ) G_{1}=\phi(G) is obtained by applying the local transformation at every vertex, then the connective constants μ ⁡ ( G ) \mu(G) and μ ⁡ ( G 1 ) \mu(G_{1}) satisfy the functional relation μ ​ ( G ) − 1 = g ⁡ ( μ ​ ( G 1 ) − 1 ) . \mu(G)^{-1}=g\bigl(\mu(G_{1})^{-1}\bigr). We next consider critical exponents defined via susceptibility-type series that do not rely on an ambient Euclidean dimension, and prove that the exponents γ \gamma and η \eta are invariant under local transformations; moreover ν \nu is invariant under a standard regularity hypothesis on SAW counts (a common slowly varying function). Our second set of results concerns bipartite graphs, where the local transformation is applied to one colour class (or to both classes, possibly with different gadgets). In this setting we obtain an analogous relation μ ​ ( G ) − 2 = h ⁡ ( μ ​ ( G e ) − 1 ) , \mu(G)^{-2}=h\bigl(\mu(G_{\mathrm{e}})^{-1}\bigr), with h ⁡ ( x ) = x ​ g ​ ( x ) h(x)=xg(x) when only one class is transformed and h ⁡ ( x ) = g ϕ 1 ​ ( x ) ​ g ϕ 2 ​ ( x ) h(x)=g_{\phi_{1}}(x)\,g_{\phi_{2}}(x) when both are transformed. We further present explicit families of examples, including replacing each degree-3 vertex by a complete-graph gadget K N K_{N} . 2010 Mathematics Subject Classification 05C30, 82B20 1. Introduction A self-avoiding walk (SAW) on a graph G is a path that visits no vertex more than once. SAWs were introduced in the chemical theory of polymerization (see Flory [ 5 ] ) and have since been central objects in probability, combinatorics, and statistical physics; see, for example, Madras and Slade [ 13 ] . For an infinite quasi-transitive graph G , the number \sigma_{n} of n -step SAWs grows exponentially, and the associated exponential growth rate \mu=\mu(G)=\lim_{n\to\infty}\sigma_{n}^{1/n} is the connective constant of G . Exact values of connective constants are known only in a small number of nontrivial cases. This paper studies how SAWs and their asymptotic parameters behave under local transformations of cubic graphs. Informally, a local transformation replaces every degree- 3 vertex by a fixed finite gadget with three distinguished outer vertices (ports) attached to the three incident edges, subject to a symmetry condition ensuring that the three ports are indistinguishable from the point of view of the gadget (Definition 3.1). A canonical example is the Fisher transformation , which replaces each vertex by a triangle; Fisher-type transformations play an important role in exact mappings between two-dimensional lattice models (e.g. Ising/dimer/vertex models) and have also been used in the SAW literature. Connective constants under local transformations. Given a local transformation \phi , we associate to the gadget a two-port generating function g(x) (Definition 3.2), defined by counting SAWs that enter the gadget through one port-edge and exit through another, while otherwise staying inside the gadget. Our first main theorem (Theorem 3.3) shows that this local data determines the connective constant of the transformed graph: if G is infinite, connected, quasi-transitive and cubic, and G_{1}=\phi(G) is obtained by applying \phi at every vertex, then (1.1) \mu(G)^{-1}=g\bigl(\mu(G_{1})^{-1}\bigr). Equivalently, \mu(G_{1})^{-1} is the unique positive solution of g(x)=\mu(G)^{-1} . This functional relation may be viewed as a substitution identity for SAW partition functions, and it extends the familiar relation arising from the Fisher transformation. Critical exponents. Beyond exponential growth, SAWs are expected to exhibit universal power-law corrections, captured by critical exponents. Rather than assuming an ambient Euclidean dimension, we work with graph-theoretic definitions of the exponents \gamma,\eta,\nu via the finiteness of natural SAW generating series (Section 3). Our second main theorem (Theorem 3.4) proves that local transformations preserve these exponents under mild hypotheses: \gamma and \eta are invariant, and \nu is invariant assuming the SAW counts satisfy a standard slowly varying correction (3.7) with a common slowly varying function. Transforming one colour class of a bipartite graph. Our third main result concerns bipartite graphs. Let G be an infinite, connected, quasi-transitive bipartite graph with colour classes (black/white), and suppose at least one class is cubic. Let G_{\mathrm{e}} be obtained by applying a local transformation to all vertices in one class (or, in the fully cubic case, applying possibly different local transformations to the two classes). Theorem 3.5 shows that the connective constants satisfy (1.2) \mu(G)^{-2}=h\bigl(\mu(G_{\mathrm{e}})^{-1}\bigr), with h(x)=xg(x) if only one class is transformed, and h(x)=g_{\phi_{1}}(x)\,g_{\phi_{2}}(x) if both classes are transformed. This yields new exact connective constants when combined with known exact values. The special case in which each cubic vertex is replaced by a triangle is the Fisher transformation . The effect of the Fisher transformation on self-avoiding walks was analyzed by Grimmett and Li [ 6 ] , who derived an explicit functional relation between the connective constants of G and its Fisher transform and proved invariance of the principal critical exponents under iteration. The present paper extends [ 6 ] from Fisher triangles to general local transformations in which each degree- 3 vertex is replaced by an arbitrary finite three-port gadget satisfying a natural symmetry condition (Definition 3.1 ). Under this general framework we obtain corresponding functional relations for connective constants (Theorems 3.3 and 3.5) and prove invariance of the critical exponents under verifiable hypotheses (Theorem 3.4), including the case where the transformation is applied to only one colour class of a bipartite graph (Theorem 3.5). . Further examples. We include explicit families of gadgets beyond Fisher triangles. In particular, replacing each cubic vertex by a complete graph K_{N} with three designated outer vertices yields an explicit polynomial g_{N}(x) (Example 6.1), and hence an explicit implicit relation between the connective constants of G and \phi^{(N)}(G) for any N\geq 3 . When N=3 , this corresponds to Fisher transformation. See Figure 1.1 for local replacements of a degree-3 vertex by a complete graph K_{3} and K_{4} . v A B C A B C Fisher (triangle) A B C K_{4} gadget Figure 1.1. Local replacement at a degree- 3 vertex: (a) the original star, (b) Fisher transformation (triangle gadget), and (c) replacement by a K_{4} gadget. See also Definition 3.1 and Figure 3.1 in the draft. A useful class of examples comes from vertex-transitive TLF-planar cubic graphs. Following Renault ( [ 14 ] ), planarity plus vertex-transitivity imposes strong geometric symmetry on embeddings: the action of graph automorphisms can (locally) be represented by isometries of the ambient geometry (spherical, Euclidean, or hyperbolic). Let G be a transitive, TLF-planar cubic graph, and let \langle a,b,c\rangle be its type-vector, i.e., the sizes of the three faces incident to a vertex, with the convention 1/\infty=0 . Define f(G):=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}. By [ 14 ] (see also [

Read the complete text