Department of Pure Mathematics and Mathematical Statistics (DPMMS)https://www.repository.cam.ac.uk/handle/1810/2137472024-05-25T17:11:24Z2024-05-25T17:11:24Z4531Phase transition for cutoff for random walks on random graphsŠarković, Andelahttps://www.repository.cam.ac.uk/handle/1810/3679152024-05-09T00:40:57Zdc.title: Phase transition for cutoff for random walks on random graphs
dc.contributor.author: Šarković, Andela
dc.description.abstract: In this thesis, we analyse the cutoff phenomenon on two different random graph models.
First, we consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has a given number of internal, degint ≥ 3, and outgoing, degout, half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and that they all have comparable sizes, we prove the following dichotomy: a simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q and log n (where n is the number of vertices) diverges.
In [5], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove that the same characterisation of cutoff holds for a simple random walk.
In the second part of the thesis, we analyse a graph G* obtained from a finite deterministic graph G = (V,E) by considering a random perfect matching of V and adding the corresponding edges to G with weight ε, while assigning weight 1 to the original edges of G. For various sequences of graphs Gn and corresponding weights εn, we establish if the (weighted) random walk on G*n has cutoff. In particular, we show a phase transition for two families of graphs, graphs with polynomial growth of balls, and graphs where the entropy of the simple random walk grows linearly up to the time of order log|Vn|. These include in particular tori, expander families and locally expanding families. We also show that this phase transition is sharp in the case of expander graphs and vertex transitive graphs with polynomial growth of balls.
Equivariant line bundles with connection on the Drinfeld upper half-space Ω⁽²⁾Zhu, Yiyuehttps://www.repository.cam.ac.uk/handle/1810/3658802024-03-20T01:41:30Zdc.title: Equivariant line bundles with connection on the Drinfeld upper half-space Ω⁽²⁾
dc.contributor.author: Zhu, Yiyue
dc.description.abstract: Ardakov and Wadsley developed a theory of $\mathscr{D}$-modules on rigid analytic spaces and established a Beilinson-Bernstein style localisation theorem for coadmissible modules over the locally analytic distribution algebra. Using this theory, they obtained admissible locally analytic representations of GL<sub>2</sub> by studying equivariant line bundles with connection on the Drinfeld half-plane Ω⁽¹⁾. In this thesis, we will follow the idea of Ardakov-Wadsley and extend their techniques to GL<sub>3</sub> by studying the Drinfeld upper half-space Ω⁽²⁾ of dimension 2.
Results in Ramsey theory and extremal graph theoryMetrebian, Roberthttps://www.repository.cam.ac.uk/handle/1810/3655202024-03-15T01:44:27Zdc.title: Results in Ramsey theory and extremal graph theory
dc.contributor.author: Metrebian, Robert
dc.description.abstract: In this thesis, we study several combinatorial problems in which we aim to find upper or lower bounds on a certain quantity relating to graphs. The first problem is in Ramsey theory, while the others are in extremal graph theory.
In Chapter 2, which is joint work with Vojtěch Dvořák, we consider the Ramsey number $R(F_n)$ of the fan graph $F_n$, a graph consisting of $n$ triangles which all share a common vertex. Chen, Yu and Zhao showed that $\frac{9}{2}n-5 \leq R(F_n) \leq \frac{11}{2}n+6$. We build on the techniques that they used to prove the upper bound of $\frac{11}{2}n+6$, and adopt a more detailed approach to examining the structure of the graph. This allows us to improve the upper bound to $\frac{31}{6}n+15$.
In Chapter 3, we work on a problem in graph colouring. Petruševski and Škrekovski recently introduced the concept of odd colouring, and the odd chromatic number of a graph, which is the smallest number of colours in an odd colouring of that graph. They showed that planar graphs have odd chromatic number at most $9$, and this bound was improved to $8$ by Petr and Portier. We consider the odd chromatic number of toroidal graphs, which are graphs that embed into a torus. By using the discharging method, along with detailed analysis of a remaining special case, we show that toroidal graphs have odd chromatic number at most $9$.
In Chapter 4, which is joint work with Victor Souza, we consider a problem in the hypercube graph $Q_n$. Huang showed that every induced subgraph of the hypercube with $2^{n-1}+1$ vertices has maximum degree at least $\lceil\sqrt{n}\rceil$, which resolved a major open problem in computer science known as the Sensitivity Conjecture. Huang asked whether analogous results could be obtained for larger induced subgraphs. For induced subgraphs of $Q_n$ with $p2^n$ vertices, we find a simple lower bound that holds for all $p$, and substantially improve this bound in the range $\frac{1}{2} < p < \frac{2}{3}$ by analysing the local structure of the graph. We also find constructions of subgraphs achieving the simple lower bound asymptotically when $p = 1-\frac{1}{r}$.
Semiparametric Methods for Two Problems in Causal Inference using Machine LearningKlyne, Harveyhttps://www.repository.cam.ac.uk/handle/1810/3638092024-01-31T01:41:26Zdc.title: Semiparametric Methods for Two Problems in Causal Inference using Machine Learning
dc.contributor.author: Klyne, Harvey
dc.description.abstract: Scientific applications such as personalised (precision) medicine require statistical guarantees on causal mechanisms, however in many settings only observational data with complex underlying interactions are available. Recent advances in machine learning have made it possible to model such systems, but their inherent biases and black-box nature pose an inferential challenge. Semiparametric methods are able to nonetheless leverage these powerful nonparametric regression procedures to provide valid statistical analysis on interesting parametric components of the data generating process.
This thesis consists of three chapters. The first chapter summarises the semiparametric and causal inference literatures, paying particular attention to doubly-robust methods and conditional independence testing. In the second chapter, we explore the doubly-robust estimation of the average partial effect — a generalisation of the linear coefficient in a (partially) linear model and a local measure of causal effect. This framework involves two plug-in nuisance function estimates, and trades their errors off against each other. The first nuisance function is the conditional expectation function, whose estimate is required to be differentiable. We propose convolving an arbitrary plug-in machine learning regression — which need not be differentiable — with a Gaussian kernel, and demonstrate that for a range of kernel bandwidths we can achieve the semiparametric efficiency bound at no asymptotic cost to the regression mean-squared error. The second nuisance function is the derivative of the log-density of the predictors, termed the score function. This score function does not depend on the conditional distribution of the response given the predictors. Score estimation is only well-studied in the univariate case. We propose using a location-scale model to reduce the problem of multivariate score estimation to conditional mean and variance estimation plus univariate score estimation. This enables the use of an arbitrary machine learning regression. Simulations confirm the desirable properties of our approaches, and code is made available in the R package drape (Doubly-Robust Average Partial Effects) available from https://github.com/harveyklyne/drape.
In the third chapter, we consider testing for conditional independence of two discrete random variables X and Y given a third continuous variable Z. Conditional independence testing forms the basis for constraint-based causal structure learning, but it has been shown that any test which controls size for all null distributions has no power against any alternative. For this reason it is necessary to restrict the null space, and it is convenient to do so in terms of the performance of machine learning methods. Previous works have additionally made strong structural assumptions on both X and Y. A doubly-robust approach which does not make such assumptions is to compute a generalised covariance measure using an arbitrary machine learning method, reducing the test for conditional correlation to testing whether an asymptotically Gaussian vector has mean zero. This vector is often high-dimensional and naive tests suffer from a lack of power. We propose greedily merging the labels of the underlying discrete variables so as to maximise the observed conditional correlation. By doing so we uncover additional structure in an adaptive fashion. Our test is calibrated using a novel double bootstrap. We demonstrate an algorithm to perform this procedure in a computationally efficient manner. Simulations confirm that we are able to improve power in high-dimensional settings with low-dimensional structure, whilst maintaining the desired size control. Code is made available in the R package catci (CATegorical Conditional Independence) available from https://github.com/harveyklyne/catci.
A Walk through the Forest: the Geometry and Topology of Random SystemsHalberstam, Noahhttps://www.repository.cam.ac.uk/handle/1810/3626182023-12-22T10:15:37Zdc.title: A Walk through the Forest: the Geometry and Topology of Random Systems
dc.contributor.author: Halberstam, Noah
dc.description.abstract: We prove several theorems on the geometry and topology of random walks and random forests, with analysis of the latter of these random systems often relying on analysis of the former and vice versa. The main models we consider are the static and dynamic random conductance models, the uniform spanning forest, the arboreal gas and countable Markov chains, and we will be interested in both the qualitative and quantitative behaviour of these systems over large scales. The quantitative properties of both the random system and its underlying medium are in this work and in general often encoded as a set of dimensions, or exponents, which govern how those properties scale asymptotically with distance or time. In addition to the analytical work above, we numerically investigate the relationships between the dimensions of fractal media and the random systems which sit upon them, and, in particular, provide evidence that universality should hold beyond the Euclidean setting. Material taken from a total of six papers is included. We also include an introduction explaining the background and context to these papers.
Random conformally covariant metrics in the planeHughes, Liamhttps://www.repository.cam.ac.uk/handle/1810/3625402023-12-22T14:45:07Zdc.title: Random conformally covariant metrics in the plane
dc.contributor.author: Hughes, Liam
dc.description.abstract: This thesis is in the broad area of random conformal geometry, combining tools from probability and complex analysis.
We mainly consider *Liouville quantum gravity* (LQG), a model introduced in the physics literature in the 1980s by Polyakov in order to provide a canonical example of a random surface with conformal symmetries and formally given by the Riemannian metric tensor "$e^{\gamma h} (dx^2+dy^2)$'' where $h$ is a Gaussian free field (GFF) on a planar domain and $\gamma \in (0,2)$. Duplantier and Sheffield constructed the $\gamma$-LQG area and boundary length measures, which fall under the framework of Kahane's Gaussian multiplicative chaos. Later, a conformally covariant distance metric associated to $\gamma$-LQG was constructed for whole-plane and zero-boundary GFFs.
In this thesis we describe the $\gamma$-LQG metric corresponding to a free-boundary GFF and derive basic properties and estimates for the boundary behaviour of the metric using GFF techniques. We use these to show that when one uses a conformal welding to glue together boundary segments of two appropriate independent LQG surfaces to get another LQG surface decorated by a *Schramm--Loewner evolution* (SLE) curve, the LQG metric on the resulting surface can be obtained as a natural metric space quotient of those on the two original surfaces. This generalizes results of Gwynne and Miller in the special case $\gamma = \sqrt{8/3}$ (for which the LQG metric can be explicitly described in terms of Brownian motion) to the entire subcritical range $\gamma \in (0,2)$. Moreover, we show that LQG metrics are infinite-dimensional (in the sense of Assouad) and thus that their embeddings into the plane cannot be quasisymmetric.
We also consider chemical distance metrics associated to *conformal loop ensembles*, the loop version of SLE, using the imaginary geometry coupling to the GFF to bound the exponent governing the conformal symmetries of such a metric.
Hitchin Functionals, h-Principles and Spectral InvariantsMayther, Laurencehttps://www.repository.cam.ac.uk/handle/1810/3619152023-12-22T14:49:37Zdc.title: Hitchin Functionals, h-Principles and Spectral Invariants
dc.contributor.author: Mayther, Laurence
dc.description.abstract: This thesis investigates Hitchin functionals and $h$-principles for stable forms on oriented manifolds, with a special focus on $\mathrm{G}_2$ and $\widetilde{\mathrm{G}}_2$ 3- and 4-forms. Additionally, it introduces two new spectral invariants of torsion-free $\mathrm{G}_2$-structures.
Part I begins by investigating an open problem posed by Bryant, $\textit{viz.}$ whether the Hitchin functional $\mathcal{H}_3$ on closed $\mathrm{G}_2$ 3-forms is unbounded above. Chapter 3 uses a scaling argument to obtain sufficient conditions for the functional $\mathcal{H}_3$ to be unbounded above and applies this result to prove the unboundedness above of $\mathcal{H}_3$ on two explicit examples of closed 7-manifolds with closed $\mathrm{G}_2$ 3-forms.
Chapter 3 then proceeds to interpret this unboundedness geometrically, demonstrating an unexpected link between the functional $\mathcal{H}_3$ and fibrations, proving that the 'large volume limit' of $\mathcal{H}_3$ in each case corresponds to the adiabatic limit of a suitable fibration. The proof utilises a new, general collapsing result for singular fibrations between orbifolds, without assumptions on curvature, which is proved in Chapter 4. Chapter 5 broadens the focus of Part I to include the Hitchin functionals $\mathcal{H}_4$, $\widetilde{\mathcal{H}}_3$ and $\widetilde{\mathcal{H}}_4$ on closed $\mathrm{G}_2$ 4-forms, $\widetilde{\mathrm{G}}_2$ 3-forms and $\widetilde{\mathrm{G}}_2$ 4-forms respectively. In its main result, Chapter 5 proves that $\mathcal{H}_4,\widetilde{\mathcal{H}}_3,\widetilde{\mathcal{H}}_4$ are always unbounded above and below (whenever defined), and also that $\mathcal{H}_3$ is always unbounded below (whenever defined). As scholia, the critical points of the functionals $\mathcal{H}_4$, $\widetilde{\mathcal{H}}_3$ and $\widetilde{\mathcal{H}}_4$ are shown to be saddle points, and initial conditions of the Laplacian coflow which cannot lead to convergent solutions are shown to be dense. Part I ends with a short discussion of open questions, in Chapter 6.
Part II investigates relative $h$-principles for closed, stable forms. After establishing some prerequisite algebraic results, Chapter 7 begins by proving that if a class of closed, stable forms satisfies the relative $h$-principle, then its corresponding Hitchin functional is automatically unbounded above. By utilising the technique of convex integration, Chapter 7 then obtains sufficient conditions for a class of closed, stable forms to satisfy the relative $h$-principle, a result which subsumes all previously established $h$-principles for closed stable forms. Until now, 12 of the 16 possible classes of closed stable forms have remained open questions with regard to the relative $h$-principle. In the main result of Part II, Chapters 7 and 8 prove the relative $h$-principle in 5 of these open cases. The remaining 7 cases are addressed in the final chapter of Part II, where it is conjectured that the relative $h$-principle holds in each case. Chapter 9 applies the $h$-principles established in this thesis to prove various results on the topological properties of closed $\widetilde{\mathrm{G}}_2$, $\mathrm{SL}(3;\mathbb{C})$ and $\mathrm{SL}(3;\mathbb{R})^2$ forms. Firstly, it characterises which oriented 7-manifolds admit closed $\widetilde{\mathrm{G}}_2$ forms, in the process introducing a new technique for proving the vanishing of natural cohomology classes on non-closed manifolds. Next, it introduces $\widetilde{\mathrm{G}}_2$-cobordisms of closed $\mathrm{SL}(3;\mathbb{C})$ and $\mathrm{SL}(3;\mathbb{R})^2$ 3-forms and proves that homotopic forms are $\widetilde{\mathrm{G}}_2$-cobordant.
Additionally, Chapter 9 classifies $\mathrm{SL}(3;\mathbb{C})$ 3-forms up to homotopy and provides a partial classification result on homotopy classes of $\mathrm{SL}(3;\mathbb{R})^2$ 3-forms. Part II ends with a short discussion of open questions, in Chapter 10.
Part III introduces and examines two new spectral invariants of torsion-free $\mathrm{G}_2$-structures.
Although the notion of an invariant is a central theme in geometry and topology, currently, there is only one known invariant of torsion-free $\mathrm{G}_2$-structures: the $\overline{\nu}$-invariant of Crowley-Goette-Nordström. Part III defines two new invariants of torsion-free $\mathrm{G}_2$-structures, termed $\mu_3$- and $\mu_4$-invariants, by regularising the classical notion of Morse index for the Hitchin functionals $\mathcal{H}_3$ and $\mathcal{H}_4$ at their critical points. In general, there is no known way to compute $\overline{\nu}$ for $\mathrm{G}_2$-manifolds constructed via Joyce's `generalised Kummer construction'. Chapter 11 obtains closed formulae for $\mu_3$ and $\mu_4$ on the orbifolds used in Joyce's construction, leading to a conjectural discussion in Chapter 12 of how to compute $\mu_3$ and $\mu_4$ on Joyce's manifolds.
Absolutely Continuous Stationary MeasuresKittle, Samuelhttps://www.repository.cam.ac.uk/handle/1810/3610442023-12-22T14:27:05Zdc.title: Absolutely Continuous Stationary Measures
dc.contributor.author: Kittle, Samuel
dc.description.abstract: This thesis studies the absolute continuity of stationary measures. Given a finite set of measurable maps $S_1, S_2, \dots, S_n$ on a measurable set $X$ and a probability vector $p_1, p_2, \dots, p_n$ we say that a probability measure $\nu$ on $X$ is stationary if
$\begin{equation*}
\nu = \sum_{i=1}^{n} p_i \nu \circ S_i^{-1}.
\end{equation*}$
If $S_1, \dots, S_n$ are elements of *PSL*<sub>2</sub>($\mathbb{R}$) acting on *X* = *P*<sup>1</sup>($\mathbb{R}$), we get the notion of Furstenberg measures. If $S_1, \dots, S_n$ are similarities, affine maps, or conformal maps then $\nu$ is called a self-similar, self-affine, or self-conformal measure respectively. This thesis is concerned with Furstenberg measures and self-similar measures.
Two fundamental questions about stationary measures are what are their dimensions and when are they absolutely continuous. This thesis deals with the second one of these.
There are several classes of stationary measures which are known to be absolutely continuous for typical choices of parameters. For example Solomyak showed that for almost every $\lambda \in (1/2, 1)$ the Bernoulli convolution with parameter $\lambda$ is absolutely continuous. This was extended by Shmerkin who showed that the exceptional set has Hausdorff dimension zero. However, despite much effort, there are relatively few known explicit examples of stationary measures which are absolutely continuous.
In this thesis we find sufficient conditions for self-similar measures and Furstenberg measures to be absolutely continuous. Using this we are able to give new examples.
The techniques we use are largely inspired by the techniques of Hochman and Varj\'u though we introduce several new ingredients the most important of which is ``detail'' which is a quantitative way of measuring how smooth a measure is at a given scale.
Homological stability of spaces of manifolds via E_k-algebrasSierra, Ismaelhttps://www.repository.cam.ac.uk/handle/1810/3610012023-12-22T14:27:05Zdc.title: Homological stability of spaces of manifolds via E_k-algebras
dc.contributor.author: Sierra, Ismael
dc.description.abstract: In this thesis we study homological stability properties of different families of spaces using the technique of cellular *E<sub>k</sub>*-algebras. Firstly, we will consider spin mapping class groups of surfaces, and their algebraic analogue —quadratic symplectic groups— using cellular *E<sub>2</sub>*-algebras. We will obtain improvements in their stability results, which for the spin mapping class groups we will show to be optimal away from the prime 2. We will also prove that in both cases the $\mathbb{F}$<sub>2</sub>-homology satisfies secondary homological stability. Finally, we will give full descriptions of the first homology groups of the spin mapping class groups and of the quadratic symplectic groups. Secondly, we will study the classifying spaces of the diffeomorphism groups of the manifolds *W*<sub>*g*,1</sub> ∶= *D*<sup>2*n*</sup>#(*S<sup>n</sup>* x *S<sup>n</sup>*)<sup>#*g*</sup>. We will get new improvements in the stability results, especially when working with rational coefficients. Moreover, we will prove a new type of stability result —quantised homological stability— which says that either the best integral stability result is a linear bound of slope 1/2 or the stability is at least as good as a line of slope 2/3.
Topics in symplectic Gromov–Witten theoryHirschi, Amandahttps://www.repository.cam.ac.uk/handle/1810/3610002023-12-22T14:27:05Zdc.title: Topics in symplectic Gromov–Witten theory
dc.contributor.author: Hirschi, Amanda
dc.description.abstract: The main focus of this thesis is on the Gromov--Witten theory of general symplectic manifolds. Mohan Swaminathan and I construct a framework to define a virtual fundamental class for the moduli space of stable maps to a general closed symplectic manifold. Our construction, inspired by [AMS21], works for all genera and leads to a more straightfoward definition of symplectic Gromov--Witten invariants as was previously available. We prove a formula for the Gromov--Witten invariants of a product of two symplectic manifolds, conjectured in [KM94].
I generalise the product formula to a formula for the Gromov--Witten invariants of a suitable fibre product of symplectic manifolds. Our invariants satisfy the Kontsevich-Manin axioms and are extended to descendent Gromov--Witten invariants. I show that our definition of Gromov--Witten invariants agrees with the classical Gromov--Witten invariants defined by [RT97] for semipositive symplectic manifolds.
Given a Hamiltonian group action on the target manifold, I construct equivariant Gromov--Witten invariants and prove a virtual Atiyah--Bott-type localisation formula, providing a tool for computations.
Together with Soham Chanda and Luya Wang, I construct infinitely many exotic Lagrangian tori in complex projective spaces of complex dimension higher than $2$. We lift tori in $\mathbb{P}$<sup>2</sup>, constructed by Vianna, and show that these lifts remain non-symplectomorphic, using an invariant derived from pseudoholomorphic disks.
Noah Porcelli and I use Ljusternik-Schnirelmann theory, applied to moduli spaces of pseudoholomorphic curves, and homotopy theory to prove lower bounds on the number of intersection points of two (possibly non-transverse) Lagrangians in terms of the cuplength of the Lagrangian in generalised cohomology theories, improving previous lower bounds by Hofer.