What is the conjecture
A self-avoiding walk (SAW) of length $n$ on a lattice $L$ (such as $\mathbb{Z}^d$) is a sequence of vertices $v_0, v_1, \ldots, v_n$ where consecutive vertices are adjacent and all vertices are distinct (the walk does not visit any vertex twice).
Let $c_n(L)$ denote the number of self-avoiding walks of length $n$ on lattice $L$.
Open Problem: Does there exist a closed-form formula or a general computable algorithm that can calculate $c_n(L)$ for arbitrary lattices $L$ and arbitrary path lengths $n$?
Currently, no such closed-form formula is known for arbitrary lattices. The connective constant $\mu(L) = \lim_{n \to \infty} (c_n(L))^{1/n}$ (which controls the exponential growth rate) has been computed for some specific lattices, but is known explicitly only for the hexagonal lattice. Computational enumeration algorithms exist and have extended computations to large path lengths (e.g., length 71 on the square lattice), but the fundamental question of whether a general closed-form formula or polynomial-time algorithm exists remains open.
Might also make sense to include the Universal Power Law Conjecture about Connective Constants, as described here https://en.wikipedia.org/wiki/Self-avoiding_walk#Universality.
(This description may contain subtle errors especially on more complex problems; for exact details, refer to the sources.)
Sources:
Prerequisites needed
Formalizability Rating: 3/5 (0 is best) (as of 2026-02-19)
Building blocks (from Mathlib):
Lattice (order-theoretic definition in Mathlib.Order.Lattice)- Graph walk and path structures (via Mathlib.Combinatorics.SimpleGraph)
- Cardinal and set operations for counting
Missing pieces:
- Formal definition of self-avoiding walks as injective sequences on lattices
- Formalization of connective constant and asymptotic growth rate
Rating justification: Core lattice and combinatorial structures exist in Mathlib, but we need to define SAW-specific structures and formalize the notion of enumeration/algorithm existence. This requires moderate new definitions but can build on existing order and graph theory infrastructure.
Choose either option
This issue was generated by an AI agent and reviewed by me.
See more information here: link
Feedback on mistakes/hallucinations: link
What is the conjecture
A self-avoiding walk (SAW) of length$n$ on a lattice $L$ (such as $\mathbb{Z}^d$ ) is a sequence of vertices $v_0, v_1, \ldots, v_n$ where consecutive vertices are adjacent and all vertices are distinct (the walk does not visit any vertex twice).
Let$c_n(L)$ denote the number of self-avoiding walks of length $n$ on lattice $L$ .
Open Problem: Does there exist a closed-form formula or a general computable algorithm that can calculate$c_n(L)$ for arbitrary lattices $L$ and arbitrary path lengths $n$ ?
Currently, no such closed-form formula is known for arbitrary lattices. The connective constant$\mu(L) = \lim_{n \to \infty} (c_n(L))^{1/n}$ (which controls the exponential growth rate) has been computed for some specific lattices, but is known explicitly only for the hexagonal lattice. Computational enumeration algorithms exist and have extended computations to large path lengths (e.g., length 71 on the square lattice), but the fundamental question of whether a general closed-form formula or polynomial-time algorithm exists remains open.
Might also make sense to include the Universal Power Law Conjecture about Connective Constants, as described here https://en.wikipedia.org/wiki/Self-avoiding_walk#Universality.
(This description may contain subtle errors especially on more complex problems; for exact details, refer to the sources.)
Sources:
Prerequisites needed
Formalizability Rating: 3/5 (0 is best) (as of 2026-02-19)
Building blocks (from Mathlib):
Lattice(order-theoretic definition in Mathlib.Order.Lattice)Missing pieces:
Rating justification: Core lattice and combinatorial structures exist in Mathlib, but we need to define SAW-specific structures and formalize the notion of enumeration/algorithm existence. This requires moderate new definitions but can build on existing order and graph theory infrastructure.
AMS categories
Choose either option
This issue was generated by an AI agent and reviewed by me.
See more information here: link
Feedback on mistakes/hallucinations: link