Subgraph Densities in Signed Graphons and the Local Simonovits–Sidorenko Conjecture

  • László Lovász

Abstract

We prove inequalities between the densities of various bipartite subgraphs in signed graphs. One of the main inequalities is that the density of any 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 was already used by Sidorenko.

Published
2011-06-14
Article Number
P127