Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 264 - Combinatorics

Dr. Balazs Szegedy

Microsoft

Limits of dense graph sequences and reflection positivity

Abstract:

We say that a sequence of dense graphs $G_n$ is convergent if for every fixed graph $F$ the density of copies of $F in G_n$ tends to a limit $f(F)$. Many theorems and conjectures in extremal graph theory can be formulated as inequalities for the possible values of the function $f$. We prove that every such inequality follows from the positive definiteness of the so-called connection matrices. Moreover we construct a natural limit object for the sequence $G_n$ namely a symmetric measurable function on the unit square. Along the line we introduce a rather general model of random graphs which seems to be interesting on its own right. \vskip .1in \noindent Joint work with L. Lovasz (Microsoft Research).

Host: Van Vu

December 7, 2004

3:00 PM

AP&M 7321

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