Problems in Extremal and Probabilistic Combinatorics

Extremal combinatorics can be described as a subfield of combinatorics that studies the maximum or minimum size of discrete structures (such as graphs, set systems, or convex bodies) with certain properties. For example, a classical question of this kind is, ``what is the maximum number of edges that a triangle-free graph can have?''. One particular beauty of extremal combinatorics lies in its connection to other fields of mathematics. That is, many questions in this area has applications in analysis, number theory, probability, and theoretical computer science. On the other hand, numerous problems which seem to be purely combinatorial can only be proved by relying on tools from algebra, analysis, topology, probability, and other areas. The most successfully developed tool among them is the so called probabilistic method. Probabilistic combinatorics on one hand refers to the study of this universal framework which can be potentially applied to any combinatorial problem and on the other hand refers to the study of random objects such as the Erdos-Renyi random graph. This field can also be described as the art of establishing certainty by adapting the language of uncertainty. These two fields, extremal and probabilistic combinatorics, share a central role in modern combinatorics and are fastly expanding; they do so by interacting with each other, and with other fields of mathematics. In this dissertation, we study several problems in these fields. These problems are chosen among the authors work in order to represent the various aspects of this field. In Chapter 2, we study a extremal problem on set systems and settle a 40 year old conjecture of Erdos and Shelah. Then in Chapters 3 and 4, we study two extremal problems using the probabilistic method, where the statement of the problem seemingly has nothing to do with probability. The first problem is a partitioning problem of graphs, and second is a problem of measuring self similarity of a graph. In Chapters 5 and 6, we study problems that lie in the intersection of extremal and probabilistic combinatorics; we take a classical theorem proved by Dirac, and further study it from various view points. These problems will illustrate the second aspect of probabilistic combinatorics.