Sidorenko's conjecture, posed by Alexander Sidorenko in 1986 in extremal graph theory, states that for any bipartite graph H and any graph G on n vertices with average degree pn, the number of labeled copies of H in G is, up to a small error term, at least what would be expected in a random graph with edge probability p. It provides an inequality about graph homomorphism densities that remains open in general.
Facts
StatementFor any bipartite graph H and graph G on n vertices with average degree pn, G contains at least p^|E(H)| n^|V(H)| labeled copies of H. 1 Proposed Year Progress Toward ResolutionOpen for general bipartite graphs; proven for paths, trees, even cycles, complete bipartite graphs and bipartite graphs with a part of at most 4 vertices. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Sidorenko's Conjecture (Wikipedia)
Sources
1. Sidorenko's Conjecture (Wikipedia)
Lead section
posed by Alexander Sidorenko in 1986
Statement
for any bipartite graph H and graph G on n vertices with average degree pn, there are at least
Known cases
Paths have Sidorenko's property, as shown by Mulholland and Smith in 1959
In Branch: Graph Theory, Lead sentence
re is a major conjecture in the field of extremal graph theory, posed by Alexander Sidorenko in 1986.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.