- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- The second eigenvalue and random walks in random regular...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
The second eigenvalue and random walks in random regular graphs with increasing girth Izsak, Alexander
Abstract
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.
Item Metadata
Title |
The second eigenvalue and random walks in random regular graphs with increasing girth
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2009
|
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.
|
Extent |
227614 bytes
|
Genre | |
Type | |
File Format |
application/pdf
|
Language |
eng
|
Date Available |
2009-09-01
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0051678
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2009-11
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International