7
$\begingroup$

I am looking for an estimation of the number of paths of length $n$ going from 0 to 0 on the hexagonal (or honeycomb) lattice.

I can find plenty on references on self avoiding paths, but I am looking into every paths. Is it considerably more difficult? Has anyone a reference?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ It should be easier: you are just looking for a diagonal entry on a power of a certain infinite adjacency matrix. $\endgroup$
    – LSpice
    Commented May 5, 2020 at 15:05
  • $\begingroup$ For any finite graph $G$, if $A$ is its adjacency matrix, then $(A^n)_{ij}$ counts the number of walks from $i$ to $j$ of length $n$. So take the adjacency matrix for the lattice up to, say, $n/2$, and compute its powers. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented May 5, 2020 at 15:05
  • 8
    $\begingroup$ This is OEIS A002898 (oeis.org/A002898). $\endgroup$
    – Richard Stanley
    Commented May 5, 2020 at 16:51

2 Answers 2

Reset to default
12
$\begingroup$

This is answered by Ian Agol here, with the reference "All Roads Lead to Rome-Even in the Honeycomb World", Brani Vidakovic, Amer. Statist. 48 (1994) no. 3, 234-236.

An exact formula is $$ p(n) = \sum_{k=0}^m \binom{2k}{k} \binom{m}{k}^2$$ if $n= 2m$ is even, and $0$ otherwise. This is sequence A002893 on OEIS.

According to OEIS, the number of paths is asymptotic to $$ p(n) \sim \frac{1}{2\pi n} 3^{n + 3/2}$$ when $n$ is even, which agrees with the estimate given by shurtados. In the above reference, Vidakovic proves that $p(n) \geq C \cdot {3^n}/{n}$ for some constant $C$.

Improve this answer
$\endgroup$
7
$\begingroup$

If you want a rough answer, it is something of the order of $\frac{3^n}{n}$. This random paths are easier than self avoiding walks, you can think of these paths in this way: If you consider the even steps, these paths describe a random walk in a triangular lattice, which is a bit easier to describe. Each step $X_i$ is given by adding a sixth root of unity $\rho^{j}$, $j= 1,2,\dots, 6$. And we want to understand when $S_n = X_1 + X_2 + \dots X_n$ is equal to zero. After $n$ steps what you have $S_n = A_n 1 + B_n\rho + C_n \rho^2 = (A_n - C_n)1 + (B_n + C_n)\rho$ (here I'm using the fact that $\rho^2 = \rho -1$). You want to estimate the probability that $A_n - C_n = 0$ and $B_n + C_n = 0$.

I think the heuristic is that $A_n, B_n, C_n$ behave like standard random walks in the line (This is also true for $A_n - C_n$, and $B_n + C_n$) and so the probability of $A_n - C_n = 0$ or that $B_n - C_n = 0$ is of the order of $\frac{1}{\sqrt{n}}$, if these events were independent this gives you $(\frac{1}{\sqrt{n}})^2 = \frac{1}{n}$.

Observe also that this answer is the same as in the square lattice, and it seems this estimate should hold for more general tilings. See also Random walk on a Penrose tiling.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.