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

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