Subgraph densities in signed graphs and local extremal graph problems

-
Laszlo Lovasz, Eotvos Lorand University, Budapest and IAS, Princeton
Fine Hall 224

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.