Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Special Combinatorics Seminar

Laszlo Lovasz

Department of Computer Science, Eotvos Lorand University

General questions about extremal graphs

Abstract:

\indent 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 an arbitrary graph? Using the theory of graph limit objects (called graphons), it is now possible to pose and in some cases answer some rather general questions about extremal graphs. - Which linear inequalities between subgraph densities are valid? Hatami and Norine very recently proved that this question is undecidable. On the other hand, it follows from results of Lovasz and Szegedy that if we allow an arbitrarily small ``slack'', then it becomes decidable. - Can all valid inequalities between subgraph densities be proved using just Cauchy-Schwarz? Using the notions of graphons and graph algebras one can give an exact formulation of this question, which turns out to be analogous to Hilbert's 17th Problem about representing nonnegative polynomials as sums of squares. Hatami and Norine showed that the answer is negative, but Lovasz and Szegedy proved that it becomes positive if we allow an arbitrarily small error. - Is there always an extremal graph? One can prove that there is always an extremal graphon, which then gives a ``template'' for asymptotically extremal graphs. - Which graphs are extremal? In other words, what are the possible "templates" of extremal graphs? There are nontrivial conditions and quite interesting families, but a complete charaterization remains an exciting but difficult open problem.

April 7, 2011

11:00 AM

NSB Auditorium

****************************