pith. sign in

arxiv: 1004.3026 · v1 · submitted 2010-04-18 · 🧮 math.CO

Subgraph densities in signed graphons and the local Sidorenko conjecture

classification 🧮 math.CO
keywords graphdensitybipartiteconjecturedensitiesedgegraphonsgraphs
0
0 comments X
read the original abstract

We prove inequalities between the densities of various bipartite subgraphs in signed graphs and graphons. One of the main inequalities is that the density of any bipartite graph with girth r cannot exceed the density of the r-cycle. This study is motivated by Sidorenko's 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.