Treffer: 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 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