Random graphs with additional structure evolving in time

Thesis

This thesis comprises three projects concerning random graphs and random processes on graphs.

In Chapter 2 we prove that if the offspring distribution of a Bienaymé tree is critical and admits a finite third moment, then under a suitable tail condition on the displacements, any globally centered size-conditioned discrete snake with finite global variance converges (upon suitable rescaling) to the Brownian snake driven by a normalized Brownian excursion. We also consider displacement distributions with heavier tails, for which we instead prove convergence in distribution to a variant of the hairy snake introduced by Janson and Marckert. We further give two applications of our main result. Namely, we obtain a scaling limit for the difference between the height function and the Łukasiewicz path of a size-conditioned critical Bienaymé tree; and we obtain a scaling limit for the difference between the height function of a size-conditioned critical Bienaymé tree and the height function of its associated looptree.

In Chapter 3 we prove a threshold for the existence of monotone increasing paths between all pairs of vertices in temporal random geometric graphs. Our result reveals that temporal connectivity appears when the edge density is significantly larger than that required for simple connectivity of the underlying graph. This contrasts with temporal connectivity thresholds for Erdős–Rényi random graphs which occur when the edge density is a constant multiple of that required for connectivity of the underlying graph. Our results hold for a wide family of soft random geometric graphs as well as the standard random geometric graph, and in general dimensions d≥2.

In Chapter 4 we prove rapid mixing for a lazy simple symmetric random walk on the set of Coxeter tournaments with a given score sequence. Coxeter tournaments serve as generalizations of standard tournaments, where in addition to competitive games, pairs of players can play collaborative games, and individual players can play solitary games. We obtain our main result by an intricate application of Bubley and Dyer’s method of path coupling, using a re-weighting of the graph metric.

Authors: MacLaine Mitchell, R

• DOI: 10.5287/ora-bpadk8wrx
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English