MathDB

Golden-mean lower-bound conjecture for connective constants of infinite vertex-transitive cubic graphs

For every infinite, connected, vertex-transitive, cubic graph GG, let cn(G,v)c_n(G,v) denote the number of self-avoiding walks of length nn starting at a vertex vv, and let the connective constant be μ(G):=lim sup⁡n→∞cn(G,v)1/n\mu(G):=\limsup_{n\to\infty} c_n(G,v)^{1/n}. Then μ(G)≥ϕ\mu(G)\geq\phi, where ϕ:=1+52\phi:=\frac{1+\sqrt{5}}{2} is the golden ratio.

Sources & referencesView supporting material

Primary source

arXiv

Additional references

graph-theoryprobabilityself-avoiding-walks

Progress summary

Refreshed
Partially solved

The conjecture remains open in general, but several important graph families now satisfy the proposed golden-ratio lower bound, including a newly strengthened conditional result for Grigorchuk graphs.

Grimmett and Li asked whether every infinite, connected, transitive cubic graph has connective constant at least the golden ratio, i.e. μ(G)≥ϕ\mu(G)\ge\phi. The question remains unresolved for the full class.

Known results

  • Graphs with a transitive graph height function satisfy μ(G)≥ϕ\mu(G)\ge\phi (Grimmett and Li, 2016).
  • The Cayley graph of the Grigorchuk group with three generators satisfies the bound (Grimmett and Li, 2016; construction attributed partly to Anton Malyshev).
  • Transitive topologically locally finite planar cubic graphs and certain two-ended cubic Cayley graphs satisfy the bound (Grimmett and Li, 2016).
  • Every two-ended vertex-transitive graph, apart from the two-way infinite path, satisfies μ(G)≥ϕ\mu(G)\ge\phi (2023).

August 2026 Grigorchuk-graph strengthening

A new preprint proves a strict version of the lower bound for Grigorchuk graphs, conditional on a stated property of their encoding sequence. This strengthens evidence for the conjecture but does not address arbitrary infinite vertex-transitive cubic graphs.

Current status (as of August 2026): The conjecture is proved for several families, with a new conditional strict result for Grigorchuk graphs, but remains open for general infinite vertex-transitive cubic graphs.

Sources

Solutions 0

No solutions have been posted yet.