I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$. Definitions from Doyle-Snell are given at the bottom of this post.

One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.

Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and that we can embed $\mathbb{Z}^3$ into a $k$-fuzz of $G$ then $G$ is transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.

What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?

I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.

EDIT:

As my audience in this talk is going to be all graph theorists, I'm mostly seeking a purely graph theoretic characterization of recurrent graphs. So for me, "infinite resistance from any point to infinity" is not good enough. I'd rather have a criterion which doesn't require me to choose an embedding and set resistances. Perhaps there is no hope of getting such an answer, but Vincent's answer below makes me believe this problem has been studied outside the context of electrical networks.

Also, based on Vincent's comment, I'm making the definitions clearer:

Doyle-Snell page 105: $G$ can be drawn in a civilized manner if its vertices can be embedded into $\mathbb{R}^d$ so that for some $0<s$ and $r< \infty$, the distance between any two points is at least $s$ and the length of each edge is $\leq r$. The drawing of such a graph need not be planar.

For any integer $k$, the $k$-fuzz of $G$ is the graph $G_k$ obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps.

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$. Definitions from Doyle-Snell are given at the bottom of this post.

One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.

Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and that we can embed $\mathbb{Z}^3$ into a $k$-fuzz of $G$ then $G$ is transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.

What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?

I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.

EDIT:

As my audience in this talk is going to be all graph theorists, I'm mostly seeking a purely graph theoretic characterization of recurrent graphs. So for me, "infinite resistance from any point to infinity" is not good enough. I'd rather have a criterion which doesn't require me to choose an embedding and set resistances. Perhaps there is no hope of getting such an answer, but Vincent's answer below makes me believe this problem has been studied outside the context of electrical networks.

Also, based on Vincent's comment, I'm making the definitions clearer:

Doyle-Snell page 105: $G$ can be drawn in a civilized manner if its vertices can be embedded into $\mathbb{R}^d$ so that for some $0<s$ and $r< \infty$, the distance between any two points is at least $s$ and the length of each edge is $\leq r$. The drawing of such a graph need not be planar.

For any integer $k$, the $k$-fuzz of $G$ is the graph $G_k$ obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps.

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$. Definitions from Doyle-Snell are given at the bottom of this post.

One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.

Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and that we can embed $\mathbb{Z}^3$ into a $k$-fuzz of $G$ then $G$ is transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.

What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?

I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.

EDIT: Based on Vincent's comment, I'm making the definitions clearer:

Doyle-Snell page 105: $G$ can be drawn in a civilized manner if its vertices can be embedded into $\mathbb{R}^d$ so that for some $0<s$ and $r< \infty$, the distance between any two points is at least $s$ and the length of each edge is $\leq r$. The drawing of such a graph need not be planar.

For any integer $k$, the $k$-fuzz of $G$ is the graph $G_k$ obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps.

I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My result works on any bounded degree locally finite graph, and I'd like to discuss the analogy to random walks there as well. Unfortunately, I've never studied random walks on graphs other than lattices. It's easy to define a random walk on an arbitrary locally finite graph (if there are $d$ edges out of $v$ then assign each probability $1/d$). Let's assume a very standard hypothesis: there is a fixed $D<\infty$ s.t. the degree of each vertex is less than $D$. Definitions from Doyle-Snell are given at the bottom of this post.

One thing which is known is Doyle and Snell's Theorem: if $G$ can be drawn in a civilized manner in $\mathbb{R}$ or $\mathbb{R}^2$ then the simple random walk on $G$ is recurrent.

Unfortunately, this leaves the question open for graphs which can't be drawn this way. An exercise in Doyle and Snell asks you to find a graph which can't be drawn this way but which is still recurrent. There is some discussion which says if a graph can be drawn in a civilized manner in $\mathbb{R}^3$ and that we can embed $\mathbb{Z}^3$ into a $k$-fuzz of $G$ then $G$ is transient. The rest of their paper gets heavily into the language of flows and I don't really understand it. It doesn't seem to finish the classification.

What's the current state of knowledge on recurrence vs. transience for random walks on a bounded degree locally finite graph? Has anyone figured this out for graphs other than those studied by the papers mentioned here?

I also found a paper by Carsten Thomassen which basically says if a graph grows slower than $\mathbb{Z}^2$ then it's recurrent (due to Nash-Williams originally) and if it satisfies an isoperimetric inequality slightly stronger than that of $\mathbb{Z}^2$ then it's transient. I don't understand this paper at all, but I'd be curious to know if it covers a larger class of graphs than Doyle and Snell's results do.

EDIT:

As my audience in this talk is going to be all graph theorists, I'm mostly seeking a purely graph theoretic characterization of recurrent graphs. So for me, "infinite resistance from any point to infinity" is not good enough. I'd rather have a criterion which doesn't require me to choose an embedding and set resistances. Perhaps there is no hope of getting such an answer, but Vincent's answer below makes me believe this problem has been studied outside the context of electrical networks.

Also, based on Vincent's comment, I'm making the definitions clearer:

Doyle-Snell page 105: $G$ can be drawn in a civilized manner if its vertices can be embedded into $\mathbb{R}^d$ so that for some $0<s$ and $r< \infty$, the distance between any two points is at least $s$ and the length of each edge is $\leq r$. The drawing of such a graph need not be planar.

For any integer $k$, the $k$-fuzz of $G$ is the graph $G_k$ obtained from $G$ by adding an edge $xy$ if it is possible to go from $x$ to $y$ in at most $k$ steps.