Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture

László Lovász

The electronic journal of combinatorics, Tome 18 (2011) no. 1

Résumé

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.

Détail

DOI : 10.37236/614

Classification : 05C42, 05C22, 05C35, 05C80
Mots-clés : density, signed graph, bipartite graph, Simonovits-Sidorenko conjecture, random graph, graphon