Skip to main content

Clique Densities

8-9 November 2017

Organiser: Katherine Staden

Please note the room change on Thursday 9th at 11am: this lecture will be in B2.01 in the Science Concourse, about 5 minutes' walk from Maths.

Christian Reiher (Hamburg)

Christian will talk about his paper The Clique Density Theorem (Annals of Mathematics). For this and other profound results in extremal and probabilistic combinatorics, Christian was one of two recipients of this year's European Prize in Combinatorics. Abstract below:

Turán's theorem is a cornerstone of extremal graph theory. It asserts that for any integer $r \geq 2$ every graph on $n$ vertices with more than $\frac{r−2}{2(r−1)}n^2$ edges contains a clique of size $r$, i.e., $r$ mutually adjacent vertices. The corresponding extremal graphs are balanced $(r−1)$-partite graphs. The question as to how many such $r$-cliques appear at least in any $n$-vertex graph with $\gamma n^2$ edges has been intensively studied in the literature. In particular, Lovász and Simonovits conjectured in the 1970s that asymptotically the best possible lower bound is given by the complete multipartite graph with $\gamma n^2$ edges in which all but one vertex class is of the same size while the remaining one may be smaller.
Their conjecture was recently resolved for $r=3$ by Razborov and for $r=4$ by Nikiforov. In this article, we prove the conjecture for all values of $r$.

Tentative schedule

This is a 4 hour mini-course.

Wednesday 8th Nov

11.00-12.00: Lecture in MS.03

12.00-13.00: Lunch in common room

13.00-14.00: Lecture in MS.03

Thursday 9th Nov

11.00-12.00: Lecture in B2.01 (Science Concourse)

12.00-13.00: Lunch in common room

13.00-14.00: Lecture in MS.04

Christian will also give the Combinatorics seminar on Friday 10 Nov, talking about Ramsey-Turán problems for cliques.

The mini-course is funded by the European Research Council and Warwick's Mathematics Institute.