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

  • László Lovász


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.

Article Number