{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T07:18:45Z","timestamp":1791530325309,"version":"4.3.4"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>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 $\\widehat \\Gamma(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 $\\Gamma(t)$ of the vacant set undergoes a phase transition in the sense of the phase transition on Erd\u00f6s--Renyi graphs $G_{n,p}$. Thus, for $r \\ge 3$ there is an explicit value $t^*=t^*(r)$ of the walk such that for $t\\leq (1-\\epsilon)t^*$, $\\Gamma(t)$ has a unique giant component, plus components of size $O(\\log n)$, whereas for $t\\geq (1+\\epsilon)t^*$ all the components of $\\Gamma(t)$ are of size $O(\\log n)$. In this paper we establish the threshold value $\\widehat t$ for a phase transition in the graph $\\widehat \\Gamma(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\\ge 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.<\/jats:p>","DOI":"10.1137\/14097937x","type":"journal-article","created":{"date-parts":[[2016,1,26]],"date-time":"2016-01-26T10:03:54Z","timestamp":1453802634000},"page":"166-205","source":"Crossref","is-referenced-by-count":1,"title":["Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk"],"prefix":"10.1137","volume":"30","author":[{"given":"Colin","family":"Cooper","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,1,26]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219199707002551"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"I. Benjamini and A. Sznitman,\n                      Giant component and vacant set for random walk on a discrete torus\n                      , J. Eur. Math. Soc. (JEMS), 10 (2008), pp. 1-40.","DOI":"10.4171\/jems\/106"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20504"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20425"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"J. C\u030cerny and A. Teixeira,\n                      From Random Walk Trajectories to Random Interlacements\n                      , Ensaios Mat. 23, Sociedade Brasilera de Mathema\u0301tica, Rio de Janeiro, 2012.","DOI":"10.21711\/217504322013\/em231"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1214\/10-AIHP407"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103428478"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20201"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20402"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.020"},{"key":"atypb13","unstructured":"W. Feller,\n                      An Introduction to Probability Theory\n                      , Vol. I, 2nd ed., Wiley, New York, 1960."},{"key":"atypb14","first-page":"910","volume":"195","author":"Friedman J.","year":"2008","journal-title":"Mem. Amer. Math. Soc."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.113"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"D. Levin, Y. Peres, and E. Wilmer,\n                      Markov Chains and Mixing Times\n                      , AMS, Providence, RI, 2008.","DOI":"10.1090\/mbk\/058"},{"key":"atypb17","unstructured":"L. Lova\u0301sz,\n                      Random walks on graphs: A survey\n                      , in Combinatorics, Paul Erdo\u0308s is Eighty, Vol. 2 (Keszthely, 1993), Ja\u0301nos Bolyai Math. Soc., Budapest, 1996, pp. 353-397."},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"M. Mihail,\n                      Conductance and convergence of Markov chains-a combinatorial treatment of expanders\n                      , in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 526-531.","DOI":"10.1109\/SFCS.1989.63529"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000552"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v13-506"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14097937X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:52:51Z","timestamp":1787316771000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14097937X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/14097937X"],"URL":"https:\/\/doi.org\/10.1137\/14097937x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}