printable pdf
比利时vs摩洛哥足彩 ,
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

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