### Mathematics Colloquium

# Christian Reiher

### (Universität Hamburg)

## "Analytical Methods in Extremal Graph Theory"

** Date: ** |
Mon, November 5, 2012 |

** Time: ** |
17:15 |

** Place: ** |
Research II Lecture Hall |

**Abstract:** Some recent developments in extremal graph theory by Lovasz and
Razborov greatly systematize the use of analytical techniques in this
area and have thereby lead to important new results some of which
answer rather old problems. In the talk we will sketch some of these
ideas and discuss their application in the recent solution to the
clique density problem obtained by the speaker.

To motivate that problem, let us recall a classical theorem due to
Mantel that tells us that any graph G on n vertices having more than
(n^2)/4 edges contains a triangle, i.e. three vertices mutually joined
by an edge. This was generalized by Turan in 1943, who obtained a
corresponding result for r-cliques instead of triangles, i.e. sets of
r vertices any two of which share an edge.

Now in the late 1970s Lovasz and Simonovits asked the more precise
question about the minimum number of r-cliques in a graph having a
given number of vertices and edges. They proposed a quite convincing
conjecture in this respect that has become known as the clique density
conjecture and proved it in very special cases. Using his differential
calculus of flag algebra homomorphisms, Razborov solved the case of
triangles in 2006, and Nikiforov added the case of 4-cliques in 2008.