Random walks on quasirandom graphs

Ben Barber; Eoin Long

Random walks on quasirandom graphs

Ben Barber, Eoin Long

Pure Mathematics

The London School of Medicine and Dentistry

Research output: Contribution to journal › Article › peer-review

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	P25
Journal	Electronic Journal of Combinatorics
Volume	20
Issue number	4
Publication status	Published - 29 Nov 2013

Keywords

Quasirandom graphs
Random walks

Access to Document

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

Cite this

@article{5ffa5b00c4ed4e40af53eeb274c86f41,

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.",

keywords = "Quasirandom graphs, Random walks",

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.

KW - Quasirandom graphs

KW - Random walks

UR - http://www.scopus.com/inward/record.url?scp=84888631780&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84888631780

SN - 1077-8926

VL - 20

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - P25

ER -

Random walks on quasirandom graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this