Sidorenko's conjecture

Conjectureopen

Sidorenko's conjecture is a major conjecture in the field of extremal graph theory, posed by Alexander Sidorenko in 1986. Roughly speaking, the conjecture states that for any bipartite graph HH and graph GG on nn vertices with average degree pnpn, there are at least pE(H)nV(H)p^{|E(H)|}n^{|V(H)|} labeled copies of HH in GG, up to a small error term. Formally, it provides an intuitive inequality about graph homomorphism densities in graphons. The conjectured inequality can be interpreted as a statement that the density of copies of HH in a graph is asymptotically minimized by a random graph, as one would expect a pE(H)p^{|E(H)|} fraction of possible subgraphs to be a copy of HH if each edge exists with probability pp.

posted by Wikipedia source: Wikipedia

0 Replies


Sign in to reply.