LIPIcs.APPROX-RANDOM.2018.45.pdf
- Filesize: 0.49 MB
- 14 pages
Document
The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree
Author
Tony Johansson 
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-13
File
Document Identifiers
Author Details
Cite AsGet BibTex
Tony Johansson. The Cover Time of a Biased Random Walk on a Random Regular Graph of Odd Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.45
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.45
Abstract
We consider a random walk process, introduced by Orenshtein and Shinkar [Tal Orenshtein and Igor Shinkar, 2014], which prefers to visit previously unvisited edges, on the random r-regular graph G_r for any odd r >= 3. We show that this random walk process has asymptotic vertex and edge cover times 1/(r-2)n log n and r/(2(r-2))n log n, respectively, generalizing the result from [Cooper et al., to appear] from r = 3 to any larger odd r. This completes the study of the vertex cover time for fixed r >= 3, with [Petra Berenbrink et al., 2015] having previously shown that G_r has vertex cover time asymptotic to rn/2 when r >= 4 is even.
Subject Classification
ACM Subject Classification
- Theory of computation → Random walks and Markov chains
Keywords
- Random walk
- random regular graph
- cover time
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in LOGSPACE. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 132-140. ACM, 1987. URL: http://dx.doi.org/10.1145/28395.28410.
- David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at URL: http://www.stat.berkeley.edu/~aldous/RWG/book.html.
- Petra Berenbrink, Colin Cooper, and Tom Friedetzky. Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time. Random Struct. Algorithms, 46(1):36-54, 2015. URL: http://dx.doi.org/10.1002/rsa.20504.
- Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Comb., 1(4):311-316, 1980. URL: http://dx.doi.org/10.1016/S0195-6698(80)80030-8.
- Colin Cooper and Alan M. Frieze. The cover time of random regular graphs. SIAM J. Discrete Math., 18(4):728-740, 2005. URL: http://dx.doi.org/10.1137/S0895480103428478.
- Colin Cooper and Alan M. Frieze. Vacant sets and vacant nets: Component structures induced by a random walk. SIAM J. Discrete Math., 30(1):166-205, 2016. URL: http://dx.doi.org/10.1137/14097937X.
- Colin Cooper, Alan M. Frieze, and Tony Johansson. The cover time of a biased random walk on a random cubic graph. To appear in Proceedings of AofA 2018, preprint available at URL: https://arxiv.org/abs/1801.00760.
- Joel Friedman. A proof of Alon’s second eigenvalue conjecture. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 720-724, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/780542.780646.
- Alan M. Frieze and Michal Karonski. Introduction to Random Graphs. Cambridge University Press, Cambridge, UK, 2015. URL: http://dx.doi.org/10.1017/CBO9781316339831.011.
- Tal Orenshtein and Igor Shinkar. Greedy random walk. Combinatorics, Probability & Computing, 23(2):269-289, 2014. URL: http://dx.doi.org/10.1017/S0963548313000552.