Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
I see you accepted my answer. Thanks for the appreciation, but in my opinion this is much too soon after you asked the question (31 minutes). Other answers might come, so why the rush... –  Did Nov 8 '11 at 5:50
    
Ok, I have another question too, is it possible to have a graph where the expected number of returns to the origin is >1, but the probability to return is <1 ? –  harry_b Nov 8 '11 at 6:58
    
Yes. The expected number of returns is p/(1-p) with p the probability to return. –  Did Nov 8 '11 at 7:08

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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