The Library
Random walks, effective resistance and neighbourhood statistics in binomial random graphs
Tools
Sylvester, John A (2017) Random walks, effective resistance and neighbourhood statistics in binomial random graphs. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Sylvester_2017.pdf - Unspecified Version - Requires a PDF viewer. Download (1500Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3190904~S1
Abstract
The binomial random graph model G(n; p), along with its near-twin sibling G(n; m), were the starting point for the entire study of random graphs and even probabilistic combinatorics as a whole. The key properties of these models are woven into the fabric of the field and their behaviour serves as a benchmark to compare any other model of random structure. In this thesis we contribute to the already rich literature on G(n; p) in a number of directions.
Firstly, vertex to vertex hitting times of random walks in G(n; p) are considered via their interpretation as potential differences in an electrical network. In particular we show that in a graph satisfying certain connectivity properties the effective resistance between two vertices is typically determined, up to lower order terms, by the degrees of these vertices. We apply this to obtain the expected values of hitting times and several related indices in G(n; p), and to prove that these values are concentrated around their mean.
We then study the statistics of the size of the r-neighbourhood of a vertex in G(n; p). We show that the sizes of these neighbourhoods satisfy a central limit theorem. We also bound the probability a vertex in G(n; p) has an r-neighbourhood of size k from above and below by functions of n; p and k which match up to constants.
Finally, in the last chapter the extreme values of the r-degree sequence are studied. We prove a novel neighbourhood growth estimate which states that with high probability the size of a vertex's r neighbourhood is determined, up to lower order terms, by the size of its first neighbourhood. We use this growth estimate to bound the number of vertices attaining a smallest r-neighbourhood.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Random walks (Mathematics), Graph theory | ||||
Official Date: | September 2017 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Georgakopoulos, Agelos ; Croydon, David A. | ||||
Sponsors: | Engineering and Physical Sciences Research Council | ||||
Extent: | v, 135 leaves | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year