Chapter 5 Extremal Combinatorics

The extremal refers to the fact that one is concerned with extremal (maximal or minimal) questions about graphs. A prototypical question is the maximal or minimal number of edges in a graph with a certain property. We have already answered such a question about maximal number of edges for a graph to be a tree.

A commonly used tool in extremal graph theory is the pigeonhole principle i.e., if a set constaining $rs+1$ elements is partitioned into $r$ classes, then one of the classes must contain at least $s+1$ elements.

It is in answering a question in extremal graph theory, Erdös made powerful use of probabilistic ideas and this gave birth to what is now famously known as the probabilistic method. We shall see an illustration of this in the later section.

We shall begin with some combinatorial results such as Erdös-Szekeres lemma and Dilworth’s lemma before moving onto applications in Graph theory such as Turan’s theorem