Random walks on quasirandom graphs

zbMATH Open1295.05213arXiv1211.3296MaRDI QIDQ396948FDOQ396948

Authors: Ben Barber, Eoin Long 

Publication date: 14 August 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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"ottcher, Hladk'y, 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.

Full work available at URL: https://arxiv.org/abs/1211.3296

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Sparse quasi-random graphs
• Quasi-randomness and the distribution of copies of a fixed graph
• scientific article; zbMATH DE number 909704
• Quasi-random graphs
• Short Random Walks on Graphs

zbMATH Keywords

random walksquasirandom graphs

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Quasi-random graphs
• Concentration of measure and isoperimetric inequalities in product spaces
• Graph colouring and the probabilistic method
• Approximate counting, uniform generation and rapidly mixing Markov chains
• The number of trees
• Pseudo-random graphs
• Title not available (Why is that?)

Cited In (6)

• An approximate version of the tree packing conjecture
• Title not available (Why is that?)
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• On the mean square displacement of a random walk on a graph
• Small subgraphs in the trace of a random walk
• Title not available (Why is that?)

This page was built for publication: Random walks on quasirandom graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396948)