General questions in extremal graph theory
Presented by László LOVáSZ
Type: Oral presentation
Track: Keynote lecture
Many questions in extremal graph theory can be phrased like this: what is the maximum of a certain linear combination of densities of given graphs in any graph G? Perhaps we have contraints on G, also in the form of fixing certain linear combinations of subgraph densities in G. Over 60-70 years, a lot of questions of this type have been posed and many have been answered. The answers are often quite difficult. For example, the minimum density of triangles, subject to fixing the edge density, was only rather recently determined by Razborov, and even more recently extended from triangles to complete 4-graphs by Nikiforov and to all complete graphs by Reiher. It is now possible to pose and in some cases answer some general questions about extremal graphs. Which inequalities between subgraph densities are valid? Can all valid inequalities be proved using just Cauchy-Schwarz? Is there always an extremal graph? Which graphs are extremal? A theory of convergent graph sequences and their limits has been worked out by Borgs, Chayes, Lovasz, Sos, Szegedy and Vesztergombi. Using this theory, such questions about extremal graphs can be posed in an exact way, and several of them can be answered in nontrivial ways. For example, Hatami and Norine proved that it is algorithmically undecidable whether a given linear inequality between subgraph densities is always valid; on the other hand, Lovasz and Szegedy proved that this question becaomes decidable if we allow an arbitrarily small error.