An approximate version of Sidorenko's conjecture

Details An approximate version of Sidorenko's conjecture An approximate version of Sidorenko's conjecture

2010-04-23

arxiv.org/abs/1004.4236v2

Mathematics

Combinatorics

12 pages

Scientific paper

A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko states that if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness. Here we prove the conjecture if H has a vertex complete to the other part, and deduce an approximate version of the conjecture for all H. Furthermore, for a large class of bipartite graphs, we prove a stronger stability result which answers a question of Chung, Graham, and Wilson on quasirandomness for these graphs.

Affiliated with

Also associated with

No associations

Rating

An approximate version of Sidorenko's conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An approximate version of Sidorenko's conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An approximate version of Sidorenko's conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-386951