Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture (Q547787): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
Summary: 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. | |||
Property / review text: Summary: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C42 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C22 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C80 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 5913185 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
density | |||
Property / zbMATH Keywords: density / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
signed graph | |||
Property / zbMATH Keywords: signed graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
bipartite graph | |||
Property / zbMATH Keywords: bipartite graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Simonovits-Sidorenko conjecture | |||
Property / zbMATH Keywords: Simonovits-Sidorenko conjecture / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
random graph | |||
Property / zbMATH Keywords: random graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
graphon | |||
Property / zbMATH Keywords: graphon / rank | |||
Normal rank |
Revision as of 12:50, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture |
scientific article |
Statements
Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture (English)
0 references
24 June 2011
0 references
Summary: 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.
0 references
density
0 references
signed graph
0 references
bipartite graph
0 references
Simonovits-Sidorenko conjecture
0 references
random graph
0 references
graphon
0 references