Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 26 / 1

A self-avoiding walk is a finite sequence of graph vertices $v_0,\dots ,v_n$ in which successive vertices are adjacent and no graph vertex is repeated; its length is $n$, the number of edges. Include the zero-length walk.

Split a length-$m+n$ walk from $v$ into its first $m$ edges and remaining $n$ edges. After fixing the first segment, the number of possible suffixes is at most ${\sigma }_n$, since forgetting the prohibition on revisiting its earlier vertices can only increase that number. Thus ${\sigma }_{m+n}(v)\le {\sigma }_m(v){\sigma }_n$, and taking the supremum givesEvery finite-radius ball is finite because degrees are bounded. An infinite connected graph has vertices arbitrarily far from each root, so shortest paths give ${\sigma }_n(v)\ge 1$. Also ${\sigma }_n\le \Delta (\Delta -1{)}^{n-1}$ for $n\ge 1$: after the first edge, an immediate reversal is forbidden. In particular $\Delta \ge 2$ and these suprema are finite.

Apply the Fekete lemma: a real subadditive sequence $a_{m+n}\le a_m+a_n$ satisfies $\lim a_n/n={\inf }_{n\ge 1}{a}_n/n$, allowing negative infinity. Here $a_n=\log {\sigma }_n\ge 0$, so the limit is finite. The uniform connective constant of a bounded-degree graph is therefore

The equal rooted counts imply that the self-avoiding walk generating function is $Z_G(x)={\sum }_{n\ge 0}{\sigma }_n{x}^n$. The Cauchy-Hadamard theorem identifies the radius of a power series $\sum a_n{x}^n$ as the reciprocal of $\mathrm{limsup}|a_n{|}^{1/n}$. ConsequentlyEquivalently, the root test gives convergence when $x\mu <1$ and divergence when $x\mu >1$. At the positive boundary $x={\mu }^{-1}$, the preceding infimum formula gives ${\sigma }_n{\mu }^{-n}\ge 1$, so this particular series diverges there as well.

The bipartite graph property means that a walk starting in $V_0$ ends there precisely when its length is even. Thus the even-length walk generating function on a bipartite graph is $Z_G^0(x)={\sum }_{k\ge 0}{\sigma }_{2k}{x}^{2k}$. Deleting the last edge of an odd-length self-avoiding walk leaves an even-length one; each such prefix has at most $\Delta$ possible last-edge choices. Hence ${\sigma }_{2k+1}\le \Delta {\sigma }_{2k}$, and for $x\ge 0$,These inequalities also hold with infinite values. Their finite positive prefactor shows that the two power series have the same radius of convergence $1/\mu$; alternatively apply the root formula to the even subsequence.

Consider a walk in the replaced graph that starts and ends in $V_0$. Each passage through a triangle enters at one port and leaves at a different port. It cannot revisit that triangle: the first passage uses at least two of its three vertices, whereas a later completed passage would need two previously unused ports. Nor can it immediately return through its entry port, since that would repeat a graph vertex. Contracting each passage therefore gives a self-avoiding walk in $G$ ending in $V_0$.

Conversely, each length-$2k$ walk of this kind in $G$ visits $k$ distinct vertices of $V_1$. At each one, its incoming and outgoing ports determine exactly two routes through the triangle: the direct internal edge or the two internal edges through the third port. Including the two external edges, these have lengths three and four. The choices at distinct triangles are independent combinatorial choices, so that walk contributes $(x^3+x^4{)}^k$ to the new generating function. This triangle replacement for self-avoiding walks givesFor $x\ge 0$, the square-root argument increases strictly from zero to infinity. Nonnegative coefficients and the radius from part (iii) therefore give the unique positive thresholdThis identifies the radius of the restricted series, without assuming that the new graph has equal counts from every graph vertex.