Justification for the conjectures on self-avoiding walks

59 Views Asked by At

There are two conjectures on self-avoiding walks that I haven't seen any justification of. One is the asymptotic growth of the number of length $n$ self-avoiding walks, the form I've seen most often is $$ c_n \sim A\mu^n n^{\gamma-1}, $$

where $A, \mu, \gamma$ are constants. Of all the literature I've seen, I haven't read about any justification for this formula, rigorous or not.

The other conjecture is stated in the Wikipedia page for self-avoiding walks and says that finding the number of such walks in a given lattice is NP-hard. There was no citation given for this, so I must ask where does this assertion appear in the literature.

Edit: Any papers referencing the NP-hardness conjecture should be about counting SAWs in the lattice $\mathbb{Z}^2$ or $\mathbb{Z}^n$