Name
Abstract | ||
|---|---|---|
Given a discrete random walk on a finite graph G, the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step t. Let Gamma(t) be the subgraph of G induced by the vacant set of the walk at step t. Similarly, let (Gamma) over cap (t) be the subgraph of G induced by the edges of the vacant net. For random r-regular graphs G(r), it was previously established that for a simple random walk the graph G(t) of the vacant set undergoes a phase transition in the sense of the phase transition on Erdos-Renyi graphs G(n,p). Thus, for r >= 3 there is an explicit value t* = t*(r) of the walk such that for t <= (1 - is an element of)t*, Gamma(t) has a unique giant component, plus components of size O(log n), whereas for t >= (1 + is an element of)t* all the components of Gamma(t) are of size O(log n). In this paper we establish the threshold value (t) over cap for a phase transition in the graph (Gamma) over cap (t) of the vacant net of a simple random walk on a random r-regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a nonbacktracking random walk and, for r even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random r-regular graphs. The main findings are the following: As r increases, the threshold for the vacant set converges to n log r in all three walks. For the vacant net, the threshold converges to rn/2 log n for both the simple random walk and the nonbacktracking random walk. When r >= 4 is even, the threshold for the vacant net of the unvisited edge process converges to rn/2, which is also the vertex cover time of the process. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1137/14097937X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
random walk,vacant set,vacant net,random regular graphs | Discrete mathematics,Binary logarithm,Graph,Combinatorics,Phase transition,Vertex (geometry),Random walk,Giant component,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 1 | 0895-4801 |
Citations | PageRank | References |
2 | 0.47 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 857 | 91.88 |
| Alan M. Frieze | 2 | 4837 | 787.00 |