Lectures on Extremal Combinatorics
In the scope of J. Griggs's invited professor position, May — June 2012
The lectures shall take place at the chevaleret building, room 1C06, according to the planning below, in a pedagogical and relaxed atmosphere.

16/05, 14h-15hJ. Griggs: Families of Subsets with a Forbidden Subposet (I)
16/05, 15h30-16h30Z. Yilma: Hypergraph Lagrangians
23/05, 14h-15hJ. Griggs: Families of Subsets with a Forbidden Subposet (II)
23/05, 15h30-16h30R. J. Kang: Asymptotics of the Erdos-Hajnal Conjecture
30/05, 14h-15hJ. Griggs: Families of Subsets with a Forbidden Subposet (III)
30/05, 15h30-16h30J.-S. Sereni: Ramsey Theory
8/06, 14h-15hJ. Griggs: Supersaturation in the Boolean Lattice
8/06, 15h30-16h30J.-S. Sereni: The Hales-Jewett Theorem


Abstracts:

Families of Subsets with a Forbidden Subposet (J. Griggs): PDF

Hypergraph Lagrangians (Z. Yilma): We discuss Turán type results obtained using graph and hypergraph Lagrangians.

Asymptotics of the Erdos-Hajnal Conjecture (R. J. Kang): The main aim is to give an introduction to the various structural and probabilistic approaches to a notorious conjecture of Erdos and Hajnal, which is concerned with understanding how the exclusion from G a fixed graph H as an induced subgraph influences the maximum size of a homogenous set in G. This area of extremal graph theory is closely related to both Ramsey theory and random graphs. Time permitting, the latter part of the talk will be devoted to some recent asymptotic formulations of the conjecture, proved using Szemerédi regularity (one of which is joint work with McDiarmid, Reed and Scott).

Ramsey Theory (J.-S. Sereni): Introductory talk to various aspects of Ramsey theory. Rather than a survey, the goal is to illustrate several ways of expressing and using Ramsey's theorem, and to give some explicit uses of the compactness principle in Ramsey theory.

Supersaturation in the Boolean Lattice (J. Griggs): If one has a collection F of subsets of the n-set [n], one can ask how many pairs of subsets A, B ("edges") must there be in F with A contained in B? We show that if |F|=C(n,n/2) +x, then there are at least xf edges, where f is \lceil (n+1)/2 \rceil, which is best-possible for small x. We are trying to solve the problem for general |F| of minimizing the number of edges in F. This would then recover a result of Kleitman(1966) that proves a conjecture of Erdos and Katona, and we hope to prove its generalization proposed by Kleitman. The talk will contain an introduction to symmetric chain decompositions of the Boolean lattice. (Joint work with J.-S. Sereni and R. J. Kang.)

The Hales-Jewett Theorem (J.-S. Sereni): The main aim is to give a proof of Hales-Jewett's theorem and see how to derive from it several important results, including van der Waerden's theorem and the Gallai—Witt theorem. We'll also state the density version of the theorem, for which a combinatorial proof was recently found.
These lectures were made possible thanks to the financial support of the University D. Diderot and the ANR project HEREDIA.