比利时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
****************************