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
****************************