A famous theorem of Mantel from 1907 states that every n-vertex graph with more than n^2/4 edges contains at least one triangle. In the 50s, Erdős asked for a quantitative version of this statement: for every n and e, how many triangles must an n-vertex e-edge graph contain?
This question has received a great deal of attention, and a long series of partial results culminated in an asymptotic solution by Razborov, extended to larger cliques by Nikiforov and Reiher. Currently, an exact solution is only known for a small range of edge densities, due to Lovász and Simonovits. In this talk, I will discuss the history of the problem and recent work which gives an exact solution for almost the entire range of edge densities. This is joint work with Hong Liu and Oleg Pikhurko.
- Combinatorial Theory Seminar