Oxford Mathematician Katherine Staden provides a fascinating snapshot of the field of combinatorics, and in particular extremal combinatorics, and the progress that she and her collaborators are making in answering one of its central questions posed by Paul Erdős over sixty years ago.
"Combinatorics is the study of combinatorial structures such as graphs (also called networks), set systems and permutations. A graph is an encoding of relations between objects, so many practical problems can be represented in graph theoretic terms; graphs and their mathematical properties have therefore been very useful in the sciences, linguistics and sociology. But mathematicians are generally concerned with theoretical questions about graphs, which are fascinating objects for their own sake. One of the attractions of combinatorics is the fact that many of its central problems have simple and elegant formulations, requiring only a few basic definitions to be understood. In contrast, the solutions to these problems can require deep insight and the development of novel tools.
A graph $G$ is a collection $V$ of vertices together with a collection $E$ of edges. An edge consists of two vertices. We can represent $G$ graphically by drawing the vertices as points in the plane and drawing a (straight) line between vertices $x$ and $y$ if $x,y$ is an edge.
Extremal graph theory concerns itself with how big or small a graph can be, given that it satisfies certain restrictions. Perhaps the first theorem in this area is due to W. Mantel from 1907, concerning triangles in graphs. A triangle is what you expect it to be: three vertices $x,y,z$ such that every pair $x,y$ and $y,z$ and $z,x$ is an edge. Consider a graph which has some number $n$ of vertices, and these are split into two sets $A$ and $B$ of size $\lfloor n/2\rfloor$, $\lceil n/2\rceil$ respectively. Now add every edge with one vertex in $A$ and one vertex in $B$. This graph, which we call $T_2(n)$, has $|A||B|=\lfloor n^2/4\rfloor$ edges. Also, it does not contain any triangles, because at least two of its vertices would have to both lie in $A$ or in $B$, and there is no edge between such pairs. Mantel proved that if any graph other than $T_2(n)$ has $n$ vertices and at least $\lfloor n^2/4\rfloor$ edges, it must contain a triangle. In other words, $T_2(n)$ is the unique `largest' triangle-free graph on $n$ vertices.
Following generalisations by P. Turán and H. Rademacher in the 1940s, Hungarian mathematician Paul Erdős thought about quantitatively extending Mantel's theorem in the 1950s. He asked the following: among all graphs with $n$ vertices and some number $e$ of edges, which one has the fewest triangles? Call this quantity $t(n,e)$. (One can also think about graphs with the most triangles, but this turns out to be less interesting).
Astoundingly, this seemingly simple question has yet to be fully resolved, 60 years later. Still, in every intervening decade, progress has been made, by Erdős, Goodman, Moon-Moser, Nordhaus-Stewart, Bollobás, Lovász-Simonovits, Fisher and others. Finally, in 2008, Russian mathematician A. Razborov managed to solve the problem asymptotically (meaning to find an approximation $g(e/\binom{n}{2})$ to $t(n,e)$ which is arbitrarily accurate as $n$ gets larger). Razborov showed that, for large $n$, $g(e/\binom{n}{2})$ has a scalloped shape: it is concave between the special points $\frac{1}{2}\binom{n}{2}, \frac{2}{3}\binom{n}{2}, \frac{3}{4}\binom{n}{2}, \ldots$. His solution required him to develop the new method of flag algebras, part of the emerging area of graph limits, which has led to the solution of many longstanding problems in extremal combinatorics.
The remaining piece of the puzzle was to obtain an exact (rather than asymptotic) solution. In recent work with Hong Liu and Oleg Pikhurko at the University of Warwick, I addressed a conjecture of Lovász and Simonovits, the solution of which would answer Erdős's question in a strong form. The conjecture put forward a certain family of $n$-vertex, $e$-edge graphs which are extremal, in the sense that they should each contain the fewest triangles. So in general there is more than one such graph, one aspect which makes the problem hard. Building on ideas of Razborov and Pikhurko-Razborov, we were able to solve the conjecture whenever $e/\binom{n}{2}$ is bounded away from $1$; in other words, as long as $e$ is not too close to its maximum possible value $\binom{n}{2}$.
Our proof spans almost 100 pages and (in contrast to Razborov's analytic proof) is combinatorial in nature, involving a type of stability argument. It would be extremely interesting to close the gap left by our work and thus fully answer Erdős's question."
Revolving captions:
The graph $T_2(n)$, which is the unique largest triangle-free graph on $n$ vertices.
The minimum number of triangles $t(n,e)$ in an $n$-vertex $e$-edge graph plotted against $e/\binom{n}{2}$. This was proved in the pioneering work of A. Razborov.
Making new graphs from old: an illustration of a step in the proof of the exact result by Liu-Pikhurko-Staden.