TY - JOUR
TI - Stability results in additive combinatorics and graph theory
DO - https://doi.org/doi:10.7282/T30R9R7B
PY - 2015
AB - A general problem in Extremal Combinatorics asks about the maximum size of a collection of finite objects satisfying certain restrictions, and an ideal solution to it presents to you the objects which attain the maximum size. In several problems, it is the case that any large set satisfying the given property must be similar to one of the few extremal examples. Such stability results give us a complete understanding of the problem, and also make the result more flexible to be applied as a tool in other mathematical problems. Stability results in additive combinatorics and graph theory constitute the main topic of this thesis, in which we solve a question of Erdös and Sarközy on sums of integers, and reprove a conjecture of Posa and Seymour on powers of hamiltonian cycles. Along the way we prove stronger structural statements that have as a corollary the optimal solution to these problems. We also introduce a counting technique and two graph theory tools which we believe to be of great interest in their own right. Namely the Shifting Method, the Connecting Lemma, and a robust version of the classic Erdos-Stone Simonovits theorem.
KW - Mathematics
KW - Combinatorial analysis
KW - Stability
KW - Graph theory
LA - eng
ER -