No phase transition for the lower-tail variational problem of bipartite graphs

For 0qp10\leq q\leq p\leq 1, let LTp(H,q)\mathsf{LT}_p(H,q) be the problem of minimizing E[Ip(W)]\mathbb{E}[I_p(W)] over graphons WW subject to t(H,W)qe(H)t(H,W)\leq q^{e(H)}, where IpI_p is the rate function and t(H,W)t(H,W) is the homomorphism density. Bipartite lower-tail conjecture. If HH is bipartite, then the constant graphon WqW\equiv q is always the unique minimizer of LTp(H,q)\mathsf{LT}_p(H,q).

The conjecture holds for every bipartite graph HH satisfying Sidorenko's conjecture, but may hold more generally. Its status is not resolved by the supplied text.

Sources & referencesView supporting material

Primary source

Yufei Zhao, “On the lower tail variational problem for random graphs”, arXiv:1502.00867 (2015).

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.