Extremal graph theory

Lecture I. Classical extremal graph theory

Extremal graph theory has several roots:applications in geometry, logic (Ramsey theory) and number theory, …

The first result in extremal graph theory is Mantel's theorem, which is Turán's theorem for K₃, see below. Next Erdős and Szekeres (re)invented Ramsey's theorem (and later they realized that it was proved a little earlier by Ramsey). Turán wanted to replace the condition of Ramsey's theorem by conditions on the edge-number: Let T_n,p be the p-class Turán graph: n vertices are partitioned into p classes as uniformly as possible and two vertices are joined iff they belong to different classes.

Theorem 1 (Turán, 1940). Among all the graphs G_n not containing K_p+1 there is only one having maximum number of edges, namely, the Turán graph T_n,p.

Erdős should have "invented extremal graph theory in 1938," but he missed it. It was important, that Turán, proving his theorem also asked several related questions.

• What is the situation for other excluded subgraphs. e.g., for the graphs of the 5 Platonic bodies?
• What is the situation for the path, loops?

This leads, among others, to the Erdős-Gallai theorem: Given a family L of (forbidden) graphs, denote by ex(n,L) the maximum number of edges a graph G_n on n vertices can have without containing subgraphs from L.

Theorem 2 (Erdős-Gallai). If P_k is a path of k vertices, ex(n,P_k)=n(k-2)/2+O(1).

Later Turán conjectured that √n is the Ramsey number: all the graphs on n vertices contain either a complete graph of ⌊√n⌋ vertices or an empty graph of this many vertices. Erdős pointed out that the right order of magnitude is not √n but c log n. This is how the random graph method emerged.

Questions from topology led to the Erdős-Stone theorem (1946) and to its important very special case, with much better estimates:

Theorem 3 (Kővári-T. Sós-Turán).

ex(n,K(a,b))≤c_a,bn^2-(1/a).

Some lower bounds were obtained

1. using graphs defined via finite geometry,
2. using random graphs,
3. using high dimensional geometric constructions, and
4. using more advanced methods from commutative algebra.

Lecture III. Regularity lemma

The famous Erdős-Turán problem on arithmetic progressions in dense sequences of integers led to a complicated version of the Szemerédi regularity lemma. Later (1976) some investigations on the quantitative Erdős-Stone theorem resulted in the modern form of the regularity lemma, one of the most powerful methods in asymptotic graph theory. This had many applications, among others, for quasi-random graphs.

The regularity lemma asserts that all graphs can be approximated - in some sense - by a generalized random graph:

Definition 4 (Generalized random graph). Given an r×r matrix A=(p_ij) where p_ij are probabilities, for x₁,…,x_r we define the corresponding generalized random graph by fixing r groups of vertices, C₁,…,C_r and joining each vertex of C_i to each (other) vertex of C_j with probability p_ij, independently.

Definition 5 (Regularity condition). Given a graph G_n and two disjoint vertex sets X⊆V, Y⊆V, we shall call the pair (X,Y) ε-regular, if for every X^*⊂X and Y^*⊂Y satisfying |X^*|>ε|X| and |Y^*|>ε|Y|,

|d(X^*,Y^*)-d(X,Y)|<ε.

Theorem 6 (Regularity Lemma 1976). For every ε>0 and ν₀ there exists a ν(ε,ν₀) such that for every G_n, V(G_n) can be partitioned into ν sets U₀, U₁,…,U_ν, for some ν₀<ν<ν(ε,ν₀), so that |U_i|=m or U_i=m+1≈n/ν for every i>0, and for all but at most ε(^ν₂) pairs (i,j) (U_i,U_j) is ε-regular. (U₀ is discarded.)

Lecture V. Some recent results

In the last lectures we shall sketch proofs of some recent results, among others, the sharp version of Luczak's theorem on the Bondy-Erdős conjecture:

Theorem 7 (Kohayakawa-Simonovits-Skokan). If C_n is an odd cycle of n vertices and R(C_n,C_n,C_n) denotes the three-color Ramsey function, then for n>n₀ R(C_n,C_n,C_n)=4n-3.

We shall also sketch the proofs of several further results and recent progress on the Erdős-Sós conjecture on trees.