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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .