Abstract:

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 labeled graphs.

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