Topics in Probabilistic Combinatorics

Abstract

This thesis consists of an introduction and eight chapters, each devoted to a different combinatorial problem. In Chapter 2, we study problems regarding reconstructing the entirety, or a large subset, of a point set $V$ embedded in either $\mathbb{R}$ or $\mathbb{R}^d$, where the only information available about $V$ consists of the pairwise distances between some of the pairs of points. In the first section, we focus on global rigidity of random graphs in $\mathbb{R}$. A graph $G$ is \emph{globally rigid} in $\mathbb{R}$ if, for any embedding of its vertices in $\mathbb{R}$, the distances along its edges uniquely determine the embedding up to isometry. We show that a random graph $G$ sampled via the Erd\H{o}s-Rényi evolution becomes globally rigid in $\mathbb{R}$ exactly at the time its minimum degree reaches $2$, confirming a conjecture posed by Benjamini and Tzalik. In the second section, we determine the sharp threshold for reconstructing a linear-sized subset of points embedded in $\mathbb{R}$. More precisely, we show that for a set $V$ of $n$ points in $\mathbb{R}$, with distances revealed according to a random graph $G(n,(1+\epsilon)/n)$, where $\epsilon>0$ is fixed, it is possible to reconstruct, up to isometry and with high probability, a subset of $V$ of size $\Omega_{\epsilon}(n)$. This confirms a conjecture posed by Gir~ao, Illingworth, Michel, Powierski, and Scott. In the third section, we investigate the analogue problem in higher dimensions. We show that for $p$ such that $p / q(n,d) \rightarrow \infty$ with $q(n,d)=n^{-1/\eta(d)+o(1)}$ and $\eta(d)=\frac{d+4}{2}-\frac{1}{d+1}$, it is possible, with high probability, to reconstruct a subset of $n-o(n)$ points of a set $V$ of size $n$ lying in $\mathbb{R}^d$, given that the pairwise distances between those points are revealed according to $G(n,p)$. This result partially answers another question posed by the same authors. Chapters 3 and 4 shift focus to finding copies of certain fixed graphs within an edge-coloured $K_n$ or a dense enough graph, with some particular properties about its edge-colouring. Chapter 3 investigates finding copies of a fixed tree $T$ in $K_n$ where some colour is over-represented, thereby resolving a question of Erdős, Füredi, Loebl, and Sós and generalising their results from two colours to multiple colours. Chapter 4 addresses the opposite problem, seeking a copy of a spanning forest of fixed isomorphic class with a close-to-balanced colouring. We prove that given any forest $F$ of order $n$ and maximum degree $\Delta$, and a balanced 2-colouring of the edges of $K_n$, then one can find an embedding of $F$ into $K_n$ whose imbalance is at most $\Delta/2 + 18$, which is essentially best possible and resolves a conjecture of Mohr, Pardey, and Rautenbach. Additionally, we provide tighter bounds for the imbalance for small values of $\Delta$. Chapter 5 to 7 delve into combinatorial games and query problems in graphs. In Chapter 5, we investigate the online Ramsey number of paths, showing that for every $k\ge 10$, the online Ramsey number for paths $P_k$ and $P_n$ satisfies $\tilde{r}(P_k,P_n) \geq \frac{5}{3}n + \frac{k}{9} - 4$. This matches up to a linear term in $k$ the upper bound recently obtained by Bednarska-Bzd{\k{e}}ga, and disproves a conjecture of Cyman, Dzido, Lapinskas and Lo. Chapter 6 explores a new algorithmic problem introduced by Ferber, Krivelevich, Sudakov, and Vieira, concerning the minimum number of queries one has to ask about adjacency between pairs of vertices of a (hidden) random graph $G \sim G(n,p)$ in order to find with high probability a subgraph that exhibits some target property. They showed that any randomised algorithm which finds a path of length $\ell=\Omega(\frac{\log(1/\epsilon)}{\epsilon})$ with at least constant probability in $G \sim G(n,p)$ where $p=\frac{1+\epsilon}{n}$ must query $\Omega(\frac{\ell}{p\epsilon\log(1/\epsilon)})$ pairs of vertices. This result is tight up to the $\log(1/\epsilon)$ factor, and they conjectured that this factor could be removed in their result. We confirm their conjecture. The main ingredient in our proof is a result regarding path-packings in random labelled trees. In Chapter 7, we are interested in a combinatorial game called the total domination game. Played on a graph $G$, the game involves two players, Dominator and Staller, alternately selecting vertices such that each chosen vertex increases the number of vertices totally dominated by the selected set. The game ends when the set of selected vertices is a total dominating set of $G$. Dominator aims to minimise the number of played moves, while Staller tries to prolong the game. We prove the 3/4-conjecture by Henning, Klav{\v{z}}ar, and Rall, stating that Dominator has a strategy to finish the total domination game on $G$ within $3n/4$ moves, where $n$ is the number of vertices of $G$. In Chapter 8 we focus on lower bounds for anti-concentration probabilities of the form $\mathbb{P}(|X|\geq x)$, where $X=\sum_{i=1}^n a_i\epsilon_i$ is a Rademacher sum; $a_i$ are positive constants normalised so that $\sum_{i=1}^n a_i^2 = 1$, and $\epsilon_i$ are independent and uniform signs $\pm 1$. We determine the value of $\inf_X \mathbb{P}(|X| \geq x)$ for all values $x\geq 0$, confirming a 1994 conjecture of Hitczenko and Kwapie{'n} and giving a partial answer to a question of Keller and Klein. We also discuss some higher-dimensional extensions of the problem. Finally, in Chapter 9, we are interested in Egyptian fractions. For a prime number $p$, we let $A_3(p)= | { m \in \mathbb{N}: \exists m_1,m_2,m_3 \in \mathbb{N}, \frac{m}{p}=\frac{1}{m_1}+\frac{1}{m_2}+\frac{1}{m_3} } |$ be the number of fractions with denominator $p$ that can be written as a ternary Egyptian fraction. Luca and Pappalardi previously established that $x (\log x)^3 \ll \sum_{p \le x} A_{3}(p) \ll x (\log x)^5$. We improve the upper bound, showing $\sum_{p \le x} A_{3}(p) \ll x (\log x)^3 (\log \log x)^2$.