Random walks on quasirandom graphs

Ben Barber; Eoin Long

Random walks on quasirandom graphs

Ben Barber, Eoin Long

Research output: Contribution to journal › Article (Academic Journal) › peer-review

4 Citations (Scopus)

178 Downloads (Pure)

Abstract

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

Original language	English
Article number	25
Number of pages	18
Journal	Electronic Journal of Combinatorics
Volume	20
Issue number	4
Publication status	Published - 29 Nov 2013

Access to Document

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via Electronic Journal of Combinatorics at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p25. Please refer to any applicable terms of use of the publisher.
Final published version, 323 KB

http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p25

Handle.net

Persistent link

Cite this

@article{6b829739c9c14cfd82b0693fecafc67f,

title = "Random walks on quasirandom graphs",

abstract = "Let G be a quasirandom graph on n vertices, and let W be a random walk on G of length αn2. Must the set of edges traversed by W form a quasirandom graph? This question was asked by B{\"o}ttcher, 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.",

author = "Ben Barber and Eoin Long",

year = "2013",

month = nov,

day = "29",

language = "English",

volume = "20",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "4",

}

TY - JOUR

T1 - Random walks on quasirandom graphs

AU - Barber, Ben

AU - Long, Eoin

PY - 2013/11/29

Y1 - 2013/11/29

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

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

M3 - Article (Academic Journal)

SN - 1077-8926

VL - 20

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - 25

ER -

Random walks on quasirandom graphs

Abstract

Access to Document

Handle.net

Fingerprint

Cite this