Random walks on quasirandom graphs

الأصل · EN

Let G be a quasirandom graph on n vertices, and let W be a random walk on G of length alpha n². 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.