Skip to main content
Open Access Publications from the University of California

Several Problems in Extremal Combinatorics

  • Author(s): Gan, Wenying
  • Advisor(s): Sudakov, Benjamin
  • et al.

Extremal combinatorics is one of the central branches of discrete mathematics. It focuses on determining or estimating the optimal possible size of a discrete structure(e.g. set systems, graphs) with certain properties. One beauty of problems in this field is that is the statements are always easy to understand, while the approaches to solve are difficult and intriguing. The other beauty is the connection with other areas like analysis, number theory, probability and computer science, namely many extremal combinatorics problems have application to these fields and the tools researchers developed in recent decades rely on these fields as well. That is why this branch of mathematics has undergone a period of a spectacular growth in the past half a century and many interesting open problems arose from it. In this dissertation, we discuss several problems in this field. These problems are chosen among the author's work in order to represent various aspect of this area.

In Chapter $2$, we study an extremal problem on set systems and partially solve an almost $50$ years old problem of Erd\H{o}s-Katona-Kleitman. In Chapter $3$, we focus on saturated bipartite graphs and prove a conjecture of Moshkovitz and Shapira up to a constant. In Chapter $4$, we study an extremal problem on graphs and verify a conjecture of Engbers and Galvin. In Chapter $5$, we provide some partial results for the generalization of the conjecture in Chapter $4$. All these researches were carried under the supervision of Benny Sudakov.

Main Content
Current View