The forcing conjecture for graphs

A graph is called forcing if it is pp-forcing for every 0<p<10<p<1, where a graph HH is pp-forcing when, for every graph sequence of edge density tending to pp, the condition tH(Gn)=(1+o(1))pE(H)t_H(G_n)=(1+o(1))p^{|E(H)|} together with the corresponding condition for K2K_2 implies quasirandomness with density pp. Forcing conjecture. A graph HH is forcing if and only if it is bipartite and contains a cycle. Bipartiteness and the presence of a cycle are necessary conditions; the conjecture proposes that they are also sufficient. The source proves the assertion for bipartite graphs having two vertices in one part complete to the other part, with that part containing at least two vertices, but leaves the general characterization open.

Sources & referencesView supporting material

Primary source

David Conlon, Jacob Fox and Benny Sudakov, “An approximate version of Sidorenko's conjecture”, arXiv:1004.4236 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.