1
$\begingroup$

A girraph is an infinite, regular, vertex-transitive graph, on which a random walk is recurrent.

The random walk on the square grid returns to the origin with probability 1, and for the cubic grid about 34%. The square grid has degree 4, and the cubic grid has degree 6.

-What is the highest degree a girraph can have?

Is there any easy way to check if a graph is a girraph?

  • 0
    Yes. The expected number of returns is p/(1-p) with p the probabilit$y$ to return.2011-11-08

1 Answers 1

3

The degree may be as large as one wants. Consider any nonempty finite set $S$ and $G=\mathbb Z\times S$ with edges between $(x,s)$ and $(y,t)$ in $G$ if and only if $|x-y|=1$. The degree of every vertex of $G$ is twice the size of $S$ and $G$ is regular and vertex transitive. To see that $G$ is recurrent, note that almost surely every $x$ in $\mathbb Z$ is visited infinitely often because the induced random walk on $\mathbb Z$ is recurrent. Furthermore, the sequence $(s_n)_n$ of the second coordinates at the times when the walk is at $x$ is i.i.d. in $S$ hence almost surely $s_n=s$ for infinitely many integers $n$, for any given $s$ in $S$. This proves that every $(x,s)$ in $G$ is visited infinitely often.

The determination of the recurrence/transience of a random walk on an infinite graph, be it regular and vertex transitive or not, is a vast subject. A classic reference is the book Random walks on infinite graphs and groups by Wolfgang Woess (expanding on an earlier, shorter, survey with a similar title by the same author).