Extremal Problems for Cycles, Paths and Set-Systems
This thesis consists of an introduction and five chapters, each devoted to a different combinatorial problem. What ties all problems considered in this thesis together is their extremal nature and the probabilistic point of view taken in their formulations or analysis. In the first three chapters we consider extremal questions regarding cycles. Cycles in graphs are one of the most natural and basic structures to study. In particular, in the context of extremal problems, questions regarding their appearance and their count has always been of a significant interest. In Chapter 2 we study the Turán number of long cycles in random and pseudo-random graphs. Denote by $ex(G(n,p),H)$ the random variable counting the number of edges in a largest subgraph of $G(n,p)$ without a copy of $H$. We determine the asymptotic value of $ex(G(n,p), C_t)$ where $C_t$ is a cycle of length $t$, for $p\geq \frac Cn$ and $A \log n \leq t \leq (1 - \varepsilon)n$, for constants $C$ and $A$. The size of $ex(G(n,p), C_t)$ depends substantially on the parity of $t$. In particular, our results match the classical result of Woodall on the Turán number of long cycles, and can be seen as its random version. This demonstrates a phenomenon known as the transference principle, introduced by Conlon and Gowers and by Schacht. In this context it can be interpreted as a random graph "inheriting'' its (relative) extremal properties from the classical deterministic case, i.e., the complete graph. In fact, our techniques apply in a more general sparse pseudo-random setting. We also prove a robustness-type result, showing the likely existence of cycles of prescribed lengths in a random subgraph of a graph with a nearly optimal density. Finally, we also present further applications of our main tool (the Key Lemma) for proving results on Ramsey-type problems about cycles in sparse random graphs. In Chapter 3 we count at least how many Hamilton cycles one can find in a hypergraph which is guaranteed to contain at least one. For $0\leq \ell <k$, a Hamilton $\ell$-cycle in a $k$-uniform hypergraph $H$ is a cyclic ordering of the vertices of $H$ in which the edges are segments of length $k$ and every two consecutive edges overlap in exactly $\ell$ vertices. We show that for all $0\le \ell<k-1$, every $k$-graph with minimum co-degree $\delta n$ with $\delta>1/2$ has (asymptotically and up to a subexponential factor) at least as many Hamilton $\ell$-cycles as a typical random $k$-graph with edge-probability $\delta$. This significantly improves a result of Glock, Gould, Joos, Kühn and Osthus, and proves a conjecture of Ferber, Krivelevich and Sudakov for all values $0\leq \ell<k-1$. In Chapter 4 we count edge-disjoint Hamilton cycles and we consider the problem of finding ``as many as possible'' in the binomial random digraph $D_{n,p}$. We show that a typical $D_{n,p}$ contains precisely the minimum of the in- and out-degrees many edge-disjoint Hamilton cycles, given that $p\geq \log^{15} n/n$, which is optimal up to a factor of polylog $n$. Our proof provides a randomised algorithm to generate the cycles and uses a novel idea of generating $D_{n,p}$ in a sophisticated way that enables us to control some key properties. In addition, we use a (relatively) recent online sprinkling idea as was introduced by Ferber and Vu. In Chapter 5 we consider online Ramsey numbers $\tilde{r}(P_k,P_n)$. We prove that for every $k\ge 10$, the online Ramsey number of paths $P_k$ and $P_n$ satisfies $\tilde{r}(P_k,P_n) \geq \frac{5}{3}n-2$, matching (up to an additive constant term) the upper bound recently obtained by Bednarska-Bzdęga, given that $k$ is fixed, and disproving a conjecture by Cyman, Dzido, Lapinskas and Lo. In Chapter 6 we address a notorious extremal problem for set systems. We focus on two types of pair $(\mathcal{A}, \mathcal{B})$ of families of subsets of an $n$-element set. We call $(\mathcal{A}, \mathcal{B})$ recovering if for any $A, A' \in \mathcal{A}$ and $B, B' \in \mathcal{B}$, the equality $A \setminus B = A' \setminus B'$ implies that $A = A'$ and $B \setminus A = B' \setminus A'$ implies that $B = B'$. We call $(\mathcal{A}, \mathcal{B})$ cancellative if for any $A, A' \in \mathcal{A}$ and $B, B' \in \mathcal{B}$, the equality $A \setminus B = A' \setminus B$ implies that $A = A'$ and $B \setminus A = B' \setminus A$ implies that $B = B'$. Simonyi conjectured that $|\mathcal{A}||\mathcal{B}| \leq 2^n$ for any recovering pair. Since Tolhuizen constructed cancellative pairs with $|\mathcal{A}| |\mathcal{B}| \geq 2.25^{n - o(n)}$, Simonyi's conjecture cannot be proven by considering cancellative pairs only. In this paper, we show that if $|\mathcal{A}| |\mathcal{B}| \leq \mu^n$ holds for all cancellative pairs, then $|\mathcal{A}| |\mathcal{B}| \leq \tau^n$ holds for all recovering pairs for some $\tau < \mu$. As a consequence, we improve the best bound on recovering pairs to $|\mathcal{A}| |\mathcal{B}| \leq 2.2543^n$. This thesis is based on joint work with Vojtĕch Dvořák, Asaf Ferber, Kaarel Haenni, Liam Hardiman, Michael Krivelevich, Gal Kronenberg, Julien Portier, Victor Souza and Leo Versteegen.
Cycles in Graphs, Extremal Combinatorics, Paths in Graphs, Random Graphs, Set-Systems
Networked Digital Library of Theses and Dissertations