Various Problems in Extremal Combinatorics

Extremal combinatorics is a central theme of discrete mathematics. It deals with the problems of finding the maximum or minimum possible cardinality of a collection of finite objects satisfying certain restrictions. These problems are often related to other areas including number theory, analysis, geometry, computer science and information theory. This branch of mathematics has developed spectacularly in the past several decades and many interesting open problems arose from it. In this dissertation, we discuss various problems in extremal combinatorics, as well as some related problems from other areas.This dissertation is organized in the way that each chapter studies a topic from extremal combinatorics, and includes its own introduction and concluding remarks. In Chapter 1 we study the relation between the chromatic number of a graph and its biclique partition, give a counterexample to the Alon-Saks-Seymour conjecture, and discuss related problems in theoretical computer science. Chapter 2 focuses on a conjecture on minimizing the number of nonnegative k-sums. Our approach naturally leads to an old conjecture by Erdos on hypergraph matchings. In Chapter 3, we improve the range that this conjecture is known to be true. Chapter 4 studies the connection of the Erdos conjecture with determining the minimum d-degree condition which guarantees the existence of perfect matching in hypergraphs. In Chapter 5, we study some extremal problems for Eulerian digraphs and obtain several results about existence of short cycles, long cycles, and subgraph with large minimum degree. The last chapter includes a proof that certain graph cut properties are quasi-random.