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.