Back to search

University of British Columbia

The second eigenvalue and random walks in random regular graphs with increasing girth

Abstract

dc:description

The goal of this thesis is to upper bound the expected value of the second largest eigenvalue in magnitude of random regular graphs with a given minimum girth. Having a small upper bound implies such random graphs are likely to be expanders and thus have several combinatorial properties useful in various fields of computer science. The best possible upper bound asymptotically on the second eigenvalue has already been proven for random regular graphs without conditions on the girth. Finding this upper bound though required long and complicated analysis due to tangles, which are certain small subgraphs that contain cycles. This thesis thus hypothesizes that specifying a minimum girth large enough will prevent tangles from occurring in random graphs and thus proving an optimal upper bound on the second eigenvalue can avoid the difficult analysis required in order to handle tangles. To find such an upper bound on random regular graphs with specified minimum girth we consider the probability that a random walk in such a random graph returns to the first vertex of the walk in the k-th step of the walk. We prove for 2-regular graphs that the random walk is more likely to visit any given vertex not in the walk than the starting vertex of the walk on the k-th step, and bound how much more likely this event is. We also analyze the d-regular case and we believe our findings will lead to a similar result in this case.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Izsak, Alexander

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/12649

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Izsak, Alexander. The second eigenvalue and random walks in random regular graphs with increasing girth. master's thesis, University of British Columbia, 2009. http://hdl.handle.net/2429/12649