Speaker
Description
Thomas Sauerwald, He Sun and Danny Vagnozzi
Abstract: A closed random walk of length $\ell$ on an undirected and connected graph G=(V,E) is a random walk that returns to the start vertex at step $\ell$, and its properties have been very 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. shows that, with high probability, the support of a closed random walk of length $\ell\geq 1$ is $\Omega(\ell^{1/5})$ on any bounded-degree graph, and leaves as an open problem whether a stronger bound of $\Omega(\ell^{1/2})$ holds for any regular graph.
First, we show that the support of a closed random walk of length $\ell$ is at least $\Omega(\ell^{1/2} / \sqrt{\log n})$ for any regular or bounded-degree graph on n vertices. Secondly, we prove for every $\ell \geq 1$ the existence of a family of bounded-degree graphs, together with a start vertex such that the support is bounded by $O( \ell^{1/2}/\sqrt{\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 $\Omega(\ell^{1/2})$ for all $\ell \geq 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 \ell)$. This rules out a general polynomial lower bound in \ell for all graphs, which is suggested in McKenzie et al. Finally, we also apply our results on random walks to obtain new bounds on the multiplicity of the second largest eigenvalue of the adjacency matrices of graphs.