Random Walk on a Graph. Part 2.

In a previous post we considered a random walk problem on a graph. For a graph G we start a walk from any vertex v_1. Every time we get to a vertex v, we exit it along an edge incident with v with equal probability. Denote by L(v_1,v_2) the event that the last new vertex is v_2, that is, when we visit v_2 all the other vertices of G are already visited and we visit v_2 for the first time. We proved that in case G is a cycle with n vertices P(L(v_1,v_2))=\frac{1}{n-1} for any two distinct vertices v_1,v_2. In this blog post we discuss a reverse result of Laszlo Lovasz and Peter Winkler [1] that there are no other non-trivial graphs with the same property. Further, I closely follow the paper [2].

Theorem. (Lovasz-Winkler, 1993, [1]). Let G be a simple connected graph with set vertices V. Denote by L(u,v), u,v\in V the event that a random walk starting at u ends at v as the last new covered vertex. Suppose

\displaystyle P(L(u,v_1))=P(L(u,v_2))\qquad (1)

holds for any vertices u,v_1,v_2\in V. Then G is either a cycle or a complete graph.

Suppose the graph G satisfies (1). It means P(L(u,v_1))=1/(|V|-1) for any u,v_1\in V, u\neq v_1. We should rule out all possibilities except G being a cycle or a complete graph. This filtering is based on two observations. The first one is a trivial, the other is also intuitive.

Observation. 1. The graph G must be 2-connected, i.e. removing any vertex of G leaves G still connected.

Indeed, suppose it’s false and removing a vertex v makes G fall apart into two components, say G_1,G_2. Take any vertices v_1\in G_1, v_2\in G_2. Then P(L(v_1,v))=0 since it’s impossible to start from v_1, visit all the other vertices of G and end up in v as the last visited new vertex – in order to visit v_2 we should pass through v first.

Observation 2. Let v_1,v_2 be two vertices of G that are not adjacent. Then there exists a neighboring vertex u of v_1 such that

\displaystyle P(L(u,v_2))\le P(L(v_1,v_2))\qquad (2).

Moreover, if after deleting v_1 and v_2, the resulting graph is still connected, then this inequality can be made strict.

Sketch of a proof. Maybe, at first look it looks complicated, but it’s not. Let’s see what happens if we assume (2) fails for all u adjacent to v_1, that is, P(L(u,v_2))> P(L(v_1,v_2)) holds for all u\in N(v_1) where N(v_1) denotes the set of neighbors of v_1. So, we start our random journey from v_1 and there is P(L(v_1,v_2)) probability that we end up at v_2 as the last new vertex.

But, after the first move, we are somewhere in N(v_1) and after that there is a greater probability that we land at v_2, moreover, we are not obliged any more to hit v_1. This is impossible. Hence, either there is u\in N(v_1) for which the inequality (2) is strict, or

\displaystyle P(L(u,v_2))= P(L(v_1,v_2))\qquad (3)

for all u\in N(v_1). Suppose now, G remains connected after removing v_1 and v_2. It means there is a path that starts from any u\in N(v_1), visits all the other vertices, except v_1 and v_2 and finally lands at v_2. This path has a certain non-zero probability to happen, which means that being in N(v_1) there is a greater probability to land at v_2 than starting from v_1. Of course this is not possible. \square

These observations are enough to narrow down the possible graphs that satisfy (1). Suppose G is a graph like that. It means

1) G is 2-connected (removing any vertex leaves the graph still connected).
2) Removing any two non-adjacent vertices of G makes it disconnected.

Now, it boils down to prove that any graph that satisfies 1) and 2) is either a cycle or a complete graph. The proof of this claim is not present in [2] and I don’t know how it was done in the original paper [1] of Lovasz and Winkler, I haven’t seen it. Here is a possible approach.
Let’s take a spanning tree T of G using depth- first-search algorithm starting from a root v_0. This algorithm guarantees T has not cross edges, i.e. all the edges of G that are not edges in T connect comparable vertices in T. If T has more than 1 leaf then those leaves are not connected (in G) and removing two of them results in still connected graph. Hence, T contains only one leaf, that is, T is a path starting from v_0 and ending at v_{n-1}. Note that v_0 and v_{n-1} should be connected (in G) because otherwise we can remove them both and the graph would be connected. Thus, there exists a cycle C=v_0v_1\dots v_{n-1}v_0 that passes through all the vertices of G. If there are no other edges, G is a cycle. Suppose it has a chord that connects v_i and v_j

Now, if there exists a pair of red and blue vertex that are not connected (see fig. 2), we can remove them and the graph would be still connected. Thus, any red point is connected to any blue one. Further, if there exist two vertices v_k,v_{\ell} that are not connected we can remove them, again contradicting the condition 2). Hence, G is a complete graph. That is it.

References.
[1] L. Lovasz and P. Winkler (1993), A Note on the Last New Vertex visited by a Random Walk, Journal of Graph Theory 17, 593–596.
[2] Tim Dwyer, Uniform distribution of last new vertex in random walk on a graph determines (almost) the graph.
[3] AoPS thread.
[4] A Random Walk on a Graph. Part 1.

2 thoughts on “Random Walk on a Graph. Part 2.”

  1. Pingback: Random Walk on a Graph. Part 1. – A Point of View.
  2. Pingback: Cycles and Chromatic Number. A Komal 2021 Problem. – A Point of View.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.