Combinatorial aspects of synchronisation, percolation, and arithmetic

Abstract

This thesis consists of an introduction and six chapters, each devoted to a different combinatorial problem. These problems cover several different directions of research in extremal, probabilistic and arithmetic combinatorics. In Chapter 2, we shall study the Kuramoto model, which is the prototypical model used for rigorous mathematical analysis in the field of synchronisation and nonlinear dynamics. A realisation of this model consists of a collection of identical oscillators with interactions given by the edges of a graph. We show that a graph with sufficient expansion must be globally synchronising, meaning that the Kuramoto model on such a graph will converge to the fully synchronised state, namely the one where all the oscillators have the same phase, for every initial state up to a set of measure zero. We show that if $\varepsilon > 0$ and $p \geq (1 + \varepsilon)(\log n)/n$, then the Kuramoto model on the Erdős-Rényi graph $G(n,p)$ is globally synchronising with probability tending to one as $n$ goes to infinity. This improves a previous result of Kassabov, Strogatz and Townsend, who have shown this with $p \gg (\log n)^2/n$, and so solve a conjecture of Ling, Xu and Bandeira. Our result is essentially best possible as $G(n,p)$ is not connected if $p = (1 - \varepsilon)(\log n)/n$. We also show that any $d$-regular Ramanujan graph is globally synchronising if $d \geq 600$. The same holds for a typical $d$-regular random graph under the same assumption on the degrees. In Chapter 3, we study a problem at the confluence of percolation theory and combinatorial game theory. The $(m,b)$ Maker-Breaker percolation game on $(\mathbb{Z}^2)_p$, introduced by Day and Falgas-Ravry, is played in the following way. Before the game starts, each edge of $\mathbb{Z}^2$ is removed independently with probability $1-p$. After that, Maker chooses a vertex $v_0$. Then, in each round, Maker and Breaker claim respectively $m$ and $b$ unclaimed edges of $G$. Breaker wins if after the removal of the edges claimed by him the component of $v_0$ becomes finite, and Maker wins if she can indefinitely prevent Breaker from winning. We show that for any $p < 1$, Breaker almost surely has a winning strategy for the $(1,1)$ game on $(\mathbb{Z}^2)_p$. This fully answers a question of Day and Falgas-Ravry, who showed that for $p = 1$ Maker has a winning strategy for the $(1,1)$ game. Further, we show that in the $(2,1)$ game on $(\mathbb{Z}^2)_p$ Maker almost surely has a winning strategy when $p > 0.9402$, while Breaker almost surely has a winning strategy when $p < 0.5278$. This shows that the threshold value of $p$ above which Maker has a winning strategy for the $(2,1)$ game on $\mathbb{Z}^2$ is non-trivial. We prove similar results in various settings, including other lattices and biases $(m,b)$. These results extend to the most general case where each edge is given to Maker with probability $\alpha$ and to Breaker with probability $\beta$ before the game starts. In Chapter 4, we are concerned with the Maclaurin inequalities for graphs, which are a broad generalisation of the classical theorems of Turán and Zykov. In a nutshell they provide an asymptotically sharp answer to the following question: what is the maximum number of cliques of size q in a $K_{r+1}$-free graph with a given number of cliques of size $s$? We prove an extensions of the graph Maclaurin inequalities with a weight function that captures the local structure of the graph. As a corollary, we settle a recent conjecture of Kirsch and Nir, which simultaneously generalise the previous localised results of Bradač; Malec and Tompkins; and the results of Kirsch and Nir. In Chapter 5, we explore multiplicative analogues of classical results in additive Ramsey theory. In particular, we are concerned with the following question: given an $r$-colouring of the interval ${2, \dotsc, N }$, what is the minimum number of monochromatic solutions of the equation $xy = z$? We give an asymptotically sharp answer for this question when $r = 2$. In this case, we also prove a stability version of this result. For general $r$, we provide polynomial upper and lower bounds on the minimum number of monochromatic solutions. For $r \leq 4$, these bounds match up to a polylogarithm factor. We also obtain results for more general multiplicative equations of the form $x_1^{a_1} \dotsb x_k^{a_k} = y$, where $a_1, \dotsc, a_k$ are fixed positive integers, at least one of which equals $1$. In Chapter 6 we are concerned with how efficiently one can encode the divisibility order. The dimension of a partially-ordered set $P$ is the smallest integer $d$ such that one can embed $P$ into a product of $d$ linear orders. We prove that the dimension of the divisibility order on the interval ${1, \dotsc, n}$ is bounded above by $C(\log n)^2 (\log \log n)^{-2} \log \log \log n$ as $n$ goes to infinity. We also provide a corresponding lower bound of $c(\log n)^2 (\log \log n)^{-2}$, asymptotically. To obtain these bounds, we provide a refinement of a bound of Füredi and Kahn and exploit a connection between the dimension of the divisibility order and the maximum size of $r$-cover-free families. In Chapter 7 we discuss an improvement upon an inequality of Croot, Dobbs, Friedlander, Hetzel and Pappalardi on the number of Egyptian fractions. We show that for all $k \geq 2$, the number of integers $1 \leq a \leq n$ such that the equation $a/n = 1/m_1 + \dotsb + 1/m_k$ has a solution in integers $1 \leq m_1 \leq \dotsb \leq m_k$ is bounded above by $n^{1 - 1/2^{k-2} + o(1)}$ as $n$ goes to infinity.