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 neartwin 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 rneighbourhood 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 rneighbourhood 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 rdegree 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 rneighbourhood.
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