School of Mathematical Sciences
Monday, December 14, 2009
Schreiber 006, 12:15
Eotvos Lorand University, Budapest
A Weak Positivstellensatz for Graphs
Many results in extremal graph theory can be proved by the combination
of a counting argument with the Cauchy-Schwarz inequality. One can
formalize these argument using an algebra of partially labeled graphs.
In this structure, one can prove an analogue of the Positivstellensatz
for graphs: Every linear inequality between subgraph densities that
holds asymptotically for all graphs has a formal proof in the following
sense: it can be approximated arbitrarily well by another valid
inequality that is a "sum of squares" in the algebra of partially
The main ingredient in the proof is the characterization of convergent
(dense) graph sequences (defined by Borgs, Chayes, Lovasz, Sos and
Vesztergombi) and their limits (constructed by Lovasz and Szegedy).
In fact, such limit objects can be described by various structures,
including certain 2-variable real functions called graphons, random
graph models satisfying certain simple consistency conditions, and
normalized, multiplicative and reflection positive graph parameters,
and probability measures on countable graphs that are ergodic with
respect to the group of permutations of the nodes.
Joint work with Balazs Szegedy (Toronto).
Coffee will be served at 12:00 before the lecture
at Schreiber building 006