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

zbMATH Open1219.05084arXiv1004.3026MaRDI QIDQ547787FDOQ547787

Authors: László Lovász 

Publication date: 24 June 2011

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1004.3026

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Subgraph densities in hypergraphs
• Signed edge \(k\)-subdomination numbers in graphs
• On substructure densities of hypergraphs
• On some graph densities in locally dense graphs
• Signed edge total \(k\)-subdomination numbers in graphs
• Local Density in Graphs with Forbidden Subgraphs
• scientific article; zbMATH DE number 2192092
• Subgraph densities in \(K_r\)-free graphs
• Signed Stark-subdomination numbers in graphs
• Density of \(C_{-4}\)-critical signed graphs

zbMATH Keywords

densityrandom graphgraphonbipartite graphsigned graphSimonovits-Sidorenko conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Density (toughness, etc.) (05C42)

Cited In (21)

• On the local approach to Sidorenko's conjecture
• A Property on Monochromatic Copies of Graphs Containing a Triangle
• Sidorenko's conjecture for blow-ups
• Inequalities for doubly nonnegative functions
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Cut distance identifying graphon parameters over weak* limits
• Tilings in graphons
• New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023
• Differential calculus on graphon space
• Non-bipartite \(k\)-common graphs
• Toward characterizing locally common graphs
• Locally common graphs
• Unified approach to the generalized Turán problem and supersaturation
• On Sidorenko's conjecture for determinants and Gaussian Markov random fields
• An approximate version of Sidorenko's conjecture
• Sparse halves in dense triangle-free graphs
• Sidorenko's conjecture, colorings and independent sets
• Matching polytons
• Diagonal Ramsey via effective quasirandomness
• Undecidability of polynomial inequalities in weighted graph homomorphism densities

This page was built for publication: Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q547787)