License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.103
URN: urn:nbn:de:0030-drops-181556
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18155/
Sauerwald, Thomas ;
Sun, He ;
Vagnozzi, Danny
The Support of Open Versus Closed Random Walks
Abstract
A closed random walk of length ? on an undirected and connected graph G = (V,E) is a random walk that returns to the start vertex at step ?, and its properties have been recently related to problems in different mathematical fields, e.g., geometry and combinatorics (Jiang et al., Annals of Mathematics '21) and spectral graph theory (McKenzie et al., STOC '21). For instance, in the context of analyzing the eigenvalue multiplicity of graph matrices, McKenzie et al. show that, with high probability, the support of a closed random walk of length ? ⩾ 1 is Ω(?^{1/5}) on any bounded-degree graph, and leaves as an open problem whether a stronger bound of Ω(?^{1/2}) holds for any regular graph.
First, we show that the support of a closed random walk of length ? is at least Ω(?^{1/2} / √{log n}) for any regular or bounded-degree graph on n vertices. Secondly, we prove for every ? ⩾ 1 the existence of a family of bounded-degree graphs, together with a start vertex such that the support is bounded by O(?^{1/2}/√{log n}). Besides addressing the open problem of McKenzie et al., these two results also establish a subtle separation between closed random walks and open random walks, for which the support on any regular (or bounded-degree) graph is well-known to be Ω(?^{1/2}) for all ? ⩾ 1. For irregular graphs, we prove that even if the start vertex is chosen uniformly, the support of a closed random walk may still be O(log ?). This rules out a general polynomial lower bound in ? for all graphs. Finally, we apply our results on random walks to obtain new bounds on the multiplicity of the second largest eigenvalue of the adjacency matrices of graphs.
BibTeX - Entry
@InProceedings{sauerwald_et_al:LIPIcs.ICALP.2023.103,
author = {Sauerwald, Thomas and Sun, He and Vagnozzi, Danny},
title = {{The Support of Open Versus Closed Random Walks}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {103:1--103:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18155},
URN = {urn:nbn:de:0030-drops-181556},
doi = {10.4230/LIPIcs.ICALP.2023.103},
annote = {Keywords: support of random walks, eigenvalue multiplicity}
}
|
Keywords: |
|
support of random walks, eigenvalue multiplicity |
|
Collection: |
|
50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
05.07.2023 |
