UCLA

Extremal combinatorics deals with the following fundamental question: how large can a structure be without containing forbidden configurations? The structures studied are extremely flexible, allowing for a wide range of applications to diverse fields such as theoretical computer science, operations research, discrete geometry and number theory. Moreover, tools from probability theory, algebra and analysis have proven incredibly useful, spurring the development of new techniques in combinatorics. This synergy between different fields has led to incredible growth in recent decades, inspiring numerous directions for research.

In this dissertation, we present new extensions of classic theorems in extremal combinatorics, employing probabilistic and analytic arguments to solve problems connected to number theory and coding theory. In Chapter 2, we greatly improve the bounds for the rainbow Turan problem for even cycles, a problem merging the graph theoretic disciplines of Turan theory and graph colouring. In Chapter 3, we use the analytic method of flag algebras to study a variant of Turan's theorem proposed by Erdos. We then shift to extremal set theory, and in Chapter 4 study the supersaturation problem for the Erdos-Ko-Rado Theorem. In Chapter 5 we discuss a probabilistic measure of supersaturation for intersecting families, introduced recently by Katona, Katona and Katona. These problems represent the various fields within extremal combinatorics that the author has worked in.