A problem of Erdos on the minimum number of k-cliques

Series
Graph Theory Seminar
Time
Tuesday, November 20, 2012 - 12:05pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jie Ma – UCLA
Organizer
Robin Thomas
Fifty years ago Erdos asked to determine the minimum number of k-cliques in a graph on n vertices with independence number less than l (we will refer this as (k,l)-problem). He conjectured that this minimum is achieved by the disjoint union of l1 complete graphs of size nl1. This conjecture was disproved by Nikiforov who showed that Erdos' conjecture can be true only for finite many pairs of (k,l). For (4,3)-problem, Nikiforov further conjectured that the balanced blow-up of a 5-cycle achieves the minimum number of 4-cliques. We first sharpen Nikiforov's result and show that Erdos' conjecture is false whenever k4 or k=3,l2074. After introducing tools (including Flag Algebra) used in our proofs, we state our main theorems, which characterize the precise structure of extremal examples for (3,4)-problem and (4,3)-problem, confirming Erdos' conjecture for (k,l)=(3,4) and Nikiforov's conjecture for (k,l)=(4,3). We then focus on (4,3)-problem and sketch the proof how we use stability arguments to get the extremal graphs, the balanced blow-ups of 5-cycle. Joint work with Shagnik Das, Hao Huang, Humberto Naves and Benny Sudakov.