Random walks on quasirandom graphs

MaRDI QIDQ396948zbMATH OpenFDO

Authors Ben Barber, Eoin Long

Publication date 14 August 2014

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

Full work available at URL https://arxiv.org/abs/1211.3296, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p25

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

zbMATH Keywords

random walksquasirandom graphs

Mathematics Subject Classification ID

Random walks on graphs (05C81)

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.

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

Cites work

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

Cited in

(6)

• An approximate version of the tree packing conjecture
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• scientific article; zbMATH DE number 1103075 (Why is no real title available?)
• scientific article; zbMATH DE number 4216772 (Why is no real title available?)
• On the mean square displacement of a random walk on a graph
• Small subgraphs in the trace of a random walk

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)