Timeline for Simple random walk on a locally finite graph: when is it recurrent?
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2022 at 17:36 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Oct 15, 2022 at 17:00 | history | edited | Glorfindel | CC BY-SA 4.0 |
broken link fixed, cf. https://meta.mathoverflow.net/q/5301/70594
|
| Dec 15, 2011 at 15:32 | vote | accept | David White | ||
| Dec 13, 2011 at 22:33 | comment | added | Ori Gurel-Gurevich | How is resistance not "purely intrinsic to the graph"? | |
| Dec 13, 2011 at 22:15 | answer | added | matan.harel | timeline score: 8 | |
| Dec 13, 2011 at 21:16 | comment | added | David White | This seems to be mostly a philosophical question. To a group who doesn't like physics much, I worry they'll lose interest if I bring in too much language involving electrical networks. They like thinking about when a graph embeds into a hypercube, so I imagine they'll be fine with nice embeddings into $\mathbb{R}^d$. Still, I'd be most happy with an answer purely intrinsic to the graph which involves neither of these methods. I'm also curious about the flows you mention, but that's just for me, not for the talk I'm giving tomorrow. | |
| Dec 13, 2011 at 21:12 | comment | added | Ori Gurel-Gurevich | (cont.) Anyway, the equivalence of recurrence and infinite resistance is far from tautological. It's not hard to prove perhaps, but not trivial either. More important though is through resistance you gain some useful tools (e.g. energy, cutsets, flows), which enable you to prove things like that recurrence is a monotone property - a subgraph of a recurrent graph is recurrent. If you want, you can take a look at some slides (math.ubc.ca/~origurel/path_slides.pdf) I made containing a crash course about random walks and electric networks (starting at slide 8). | |
| Dec 13, 2011 at 21:06 | comment | added | Ori Gurel-Gurevich | Now I'm even more confused. First you mention that you want something "purely graph theoretical" not requiring embeddings and whatnot, then you say that your audience will not appreciate the resistance criteria (which is purely graph theoretical) so much and will like the "civilized" result much more, even though this result does require embeddings. | |
| Dec 13, 2011 at 19:50 | comment | added | David White | Thanks for all the comments, Ori. Perhaps my choice of wording in the edit was not optimal. I'm seeking a way to present this material that my audience will appreciate and I know they won't like the answer about resistance as it seems too tautological, due to the equivalent definitions. They would like the "civilized" result much more, but that is not a complete classification. If recent work has helped make it more complete, I'd like to know. Or if someone else has found a different way to classify recurrent graphs without reference to electrical resistance, then that would also satisfy me. | |
| Dec 13, 2011 at 18:57 | comment | added | Ori Gurel-Gurevich | @David, reading your edit, I think there's some misunderstanding here. The definition of resistance is purely graph theoretic. There is no embedding required. | |
| Dec 13, 2011 at 18:45 | history | edited | David White | CC BY-SA 3.0 |
Clarified what I was looking for in an answer
|
| Dec 13, 2011 at 18:30 | comment | added | David White | Ah, nevermind. I have now corrected my error above, thanks for pointing it out. The $s$ condition is not about lengths of edges it's about distance in $\mathbb{R}^d$ and I had missed that. | |
| Dec 13, 2011 at 18:30 | history | edited | David White | CC BY-SA 3.0 |
Made definitions clearer
|
| Dec 13, 2011 at 18:28 | answer | added | Ori Gurel-Gurevich | timeline score: 18 | |
| Dec 13, 2011 at 18:24 | comment | added | David White | @Vincent: Could you clarify what you mean in this comment? The definition I put above (and have now edited to make it clearer) is taken directly from Doyle and Snell. I would think the requirement that every edge has length greater than a constant $s>0$ would be enough to ensure this well-separatedness. Is that right? | |
| Dec 13, 2011 at 17:53 | answer | added | Stephen Shea | timeline score: 1 | |
| Dec 13, 2011 at 17:26 | answer | added | Vincent Beffara | timeline score: 12 | |
| Dec 13, 2011 at 17:15 | comment | added | Vincent Beffara | Just a minor point of vocabulary: in the definition of "civilized", you need the edges to be short but you also need the points to be well separated (without that it is easy to draw a very large tree in $\mathbb Z^2$ with all edges of the same length, and that would be transient ...) | |
| Dec 13, 2011 at 16:36 | answer | added | Igor Rivin | timeline score: 1 | |
| Dec 13, 2011 at 16:24 | history | asked | David White | CC BY-SA 3.0 |