University of British Columbia
The second eigenvalue and random walks in random regular graphs with increasing girth
Abstract
dc:descriptionThe 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