Random Walks on Quasirandom Graphs

  • Ben Barber
  • Eoin Long
Keywords: Random walks, Quasirandom graphs

Abstract

Let $G$ be a quasirandom graph on $n$ vertices, and let $W$ be a random walk on $G$ of length $\alpha n^2$. Must the set of edges traversed by $W$ form a quasirandom graph? This question was asked by Böttcher, Hladký, Piguet and Taraz. Our aim in this paper is to give a positive answer to this question. We also prove a similar result for random embeddings of trees.

Published
2013-11-29
Article Number
P25