Conjecture For any bipartite graph and graph , the number of homomorphisms from to is at least .
A homomorphism from a graph to a graph is a mapping which preserves edges. Given graphs and , the homomorphism density of in , denoted , is the probability that a random function is a homomorphism. That is,
In this language, Sidorenko's Conjecture says that, if is bipartite, then every graph satisfies
There are lots of results on Sidorenko's Conjecture; rather than listing them all here, we encourage the reader to see the references of the recent paper [CL].
Bibliography
[CL] David Conlon and Joonkyung Lee: Sidorenko's conjecture for blow-ups, submitted.
* indicates original appearance(s) of problem.