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

At least 10 years old · documented by

For 0≤q≤p≤10\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 W≡qW\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.

References

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.