Extremal Problems for Cycles, Paths and Set-Systems
type: CreativeWork
description: 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 a…
abstract: 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 a…
author: Mond, Adva
language: eng
keywords: Cycles in Graphs, Extremal Combinatorics, Paths in Graphs, Random Graphs, Set-Systems
license: https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/b462f339-19e9-4548-aab6-088694776b34/download
license: https://www.rioxx.net/licenses/all-rights-reserved/
date published: 2024-07-11
date modified: 2026-07-22T22:24:04Z
provider: Cambridge University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Cambridge

PropertyValue
property ID: DOI
value: 10.17863/CAM.112805