Relevant Thesis-Based Degree Programs
Graduate Student Supervision
Doctoral Student Supervision
Dissertations completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest dissertations.
This thesis investigates the large-scale behaviour emerging in two discrete models: the uniform spanning tree on ℤ³ and the chase-escape with death process.We consider the uniform spanning tree (UST) on ℤ³ as a measured, rooted real tree, continuously embedded into Euclidean space. The main result is on the existence of sub-sequential scaling limits and convergence under dyadic scalings. We study properties of the intrinsic distance and the measure of the sub-sequential scaling limits, and the behaviour of the random walk on the UST. An application of Wilson’s algorithm, used in the study of scaling limits, is also instrumental in a related problem. We show that the number of spanning clusters of the three-dimensional UST is tight under scalings of the lattice.Chase-escape is a competitive growth process in which red particles spread to adjacent uncoloured sites while blue particles overtake adjacent red particles. We propose a variant of the chase-escape process called chase-escape with death (CED). When the underlying graph of CED is a d-ary tree, we show the existence of critical parameters and characterize the phase transitions.
This thesis concerns critical branching random walks. We focus on supercritical (d ≥ 5 or higher) and critical (d=4) dimensions. In this thesis, we extend the potential theory for random walk to critical branching random walk. In supercritical dimensions, we introduce branching capacity for every finite subset of ℤ^d and construct its connections with critical branching random walk through the following three perspectives. 1. The visiting probability of a finite set by a critical branching random walk starting far away; 2. Branching recurrence and branching transience; 3. Local limit of branching random walk in torus conditioned on the total size. Moreover, we establish the model which we call 'branching interlacements' as the local limit of branching random walk in torus conditioned on the total size. In the critical dimension, we also construct some parallel results. On the one hand, we give the asymptotics of visiting a finite set and the convergence of the conditional hitting point. On the other hand, we establish the asymptotics of the range of a branching random walk conditioned on the total size. Also in this thesis, we analyze a small game which we call the Majority-Markov game and give an optimal strategy.
We prove several theorems concerning random walks, harmonic functions, percolation, uniform spanning forests, and circle packing, often in combination with each other. We study these models primarily on planar graphs, on transitive graphs, and on unimodular random rooted graphs, although some of our results hold for more general classes of graphs. Broadly speaking, we are interested in the interplay between the geometry of a graph and the behaviour of probabilistic processes on that graph. Material taken from a total of nine papers is included. We have also included an extended introduction explaining the background and context to these papers.
This thesis investigates the geometry of random spaces. Geodesics in random surfaces. The Brownian map, developed by Le Gall and Miermont, is a random metric space arising as the scaling limit of random planar maps. Its construction involves Aldous’ continuum random tree, the canonical random real tree, and Brownian motion, an almost surely continuous but nowhere differentiable path. As a result, the Brownian map is a non-differentiable surface with a fractal geometry that is much closer to that of a real tree than a smooth surface. A key feature, observed by Le Gall, is the confluence of geodesics phenomenon, which states that any two geodesics to a typical point coalesce before reaching the point. We show that, in fact, geodesics to anywhere near a typical point pass through a common confluence point. This leads to information about special points that had remained largely mysterious. Our main result is the almost everywhere continuity and uniform stability of the cut locus of the Brownian map. We also classify geodesic networks that are dense and find the Hausdorff dimension of the set of pairs that are joined by each type of network. Susceptibility of random graphs. Given a graph G=(V,E) and an initial set I of active vertices in V, the r-neighbour bootstrap percolation process, attributed to Chalupa, Leath and Reich, is a cellular automaton that evolves by activating vertices with at least r active neighbours. If all vertices in V are activated eventually, we say that I is contagious. A graph with a small contagious set is called susceptible. Bootstrap percolation has been analyzed on several deterministic graphs, such as grids, lattices and trees. More recent work studies the model on random graphs, such as the fundamental Erdős–Rényi graph G(n,p). We identify thresholds for the susceptibility of G(n,p), refining approximations by Feige, Krivelevich and Reichman. Along the way, we obtain large deviation estimates that complement central limit theorems of Janson, Łuczak, Turova and Vallier. We also study graph bootstrap percolation, a variation due to Bollobás. Our main result identifies the sharp threshold for K4-percolation, solving a problem of Balogh, Bollobás and Morris.
Random planar maps have been an object of utmost interest over the lastdecade and half since the pioneering works of Benjamini and Schramm, Angel and Schramm and Chassaing and Schaeffer. These maps serve as modelsof random surfaces, the study of which is very important with motivationsfrom physics, combinatorics and random geometry.Uniform infinite planar maps, introduced by Angel and Schramm, whichare obtained as local limits of uniform finite maps embedded in the sphere,serve as a very important discrete model of infinite random surfaces. Recently, there has been growing interest to create and understand hyperbolicversions of such uniform infinite maps and several conjectures and proposedmodels have been around for some time. In this thesis, we mainly addressthese questions from several viewpoints and gather evidence of their existence and nature.The thesis can be broadly divided into two parts. The first part isconcerned with half planar maps (maps embedded in the upper half plane)which enjoy a certain domain Markov property. This is reminiscent of thatof the SLE curves. Chapters 2 and 3 are mainly concerned with classi cationof such maps and their study, with a special focus on triangulations. Thesecond part concerns investigating unicellular maps or maps with one faceembedded in a high genus surface. Unicellular maps are generalizations oftrees in higher genera. The main motivation is that investigating such mapswill shed some light into understanding the local limit of general maps viasome well-known bijective techniques. We obtain certain information aboutthe large scale geometry of such maps in Chapter 4 and about the local limitof such maps in Chapter 5.
This thesis consists of four research papers and one expository note that study factors of point processes in the contexts of thinning and matching.In "Poisson Splitting by Factors," we prove that given a Poisson point process on Rd with intensity λ, as a deterministic function of the process, we can colour the points red and blue, so that each colour class forms a Poisson point process on Rd, with any given pair of intensities summing λ; furthermore, the function can be chosen as an isometry-equivariant finitary factor (that is, if an isometry is applied to the points of the original process the points are still coloured the same way). Thus using only local information, without a central authority or additionalrandomization, points of a Poisson process can split into two groups, each of which are still Poisson.In "Deterministic Thinning of Finite Poisson Processes," we investigate similar questions for Poisson point processes on a finite volume. In this setting we find that even without considerations of equivariance, thinning can not always be achieved as a deterministic function of the Poisson process and the existence of such a function depends on the intensities of the original and resulting Poisson process. In "Insertion and Deletion Tolerance of Point Processes," we define for point processes a version of the concept of finite-energy. This simple concept has many interesting consequences. We explore the consequences of having finite-energy in the contexts of the Boolean continuum percolation model, Palm theory and stable matchings of point processes.In "Translation-Equivariant Matchings of Coin-Flips on Zd," as a factor of i.i.d. fair coin-flips on Zd, we construct perfect matchings of heads and tails and prove power law upper bounds on the expected distance between matched pairs.In the expository note "A Nonmeasurable Set from Coin-Flips," using the notion of an equivariant function, we give an example of a nonmeasurable set in the probability space for an infinite sequence of coin-flips.
Master's Student Supervision
Theses completed in 2010 or later are listed below. Please note that there is a 6-12 month delay to add the latest theses.
Let Tn be a uniformly randomly selected word of size n from an irreducible unambiguous context-free grammar $H$. We analyze the number of times of seeing a fixed pattern within Tn by constructing a critical multitype branching process (on the context free grammar) that assigns the same probability to words of the same size (if the grammar is regular, then we construct such a Markov chain instead). We give an easy way to compute the density constants of expectations for any given pattern. We also give a lower bound for the density constant of the variance in the case that the given pattern is replaceable by another pattern. Using fringe convergence results from Stufler's paper, we show that a uniformly selected fringe subtree from a uniformly selected derivation tree converges to the unconditioned branching process.