- 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 l−1 complete graphs of size nl−1.
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 k≥4 or k=3,l≥2074. 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.