***********************************
                * Princeton Discrete Math Seminar *
                ***********************************


Date: Thursday 20th October, 2.15 in Fine Hall 224
 
Speaker: Laszlo Lovasz, Eotvos Lorand University, Budapest and IAS, Princeton 

Title: Subgraph densities in signed graphs and local extremal graph problems

Let G be a graph whose edges are signed by +1 or -1. We can
"count" labeled copies of a graph F in G by multiplying the
edge signatures and summing over all copies of F. The density of
F in G is obtained by dividing by the total number of maps
from V(F) to V(G).

There are interesting inequalities between the densities of
various subgraphs in signed graphs. One of the main
inequalities is that the density of a bipartite graph
with girth 2r cannot exceed the density of the 2r-cycle.

This study is motivated by the Simonovits--Sidorenko conjecture,
which states that the density of a bipartite graph F with
m edges in any graph G is at least the m-th power of
the edge density of G. Another way of stating this is that
the graph G with given edge density minimizing the number of
copies of F is, asymptotically, a random graph. We prove that
this is true locally, i.e., for graphs G that are ``close''
to a random graph.

Both kinds of results are treated in the framework of graphons
(2-variable functions serving as limit objects for graph sequences),
which in this context were already used by Sidorenko.

                       -----------

Next week: Stefan van Zwam.

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)