The bipartite lower-tail conjecture in the sparse limit

About 11 years old · traced to

Let HH be a graph and 0≤r≤10\leq r\leq 1. Define h(x)=xlog⁡x−x+1h(x)=x\log x-x+1 and let LT(H,r)\mathsf{LT}(H,r) be the problem of minimizing E[h(W)]\mathbb{E}[h(W)] over graphons WW subject to t(H,W)≤re(H)t(H,W)\leq r^{e(H)}. Sparse bipartite conjecture. For every bipartite graph HH and every 0≤r≤10\leq r\leq 1, the constant graphon W≡rW\equiv r is the unique minimizer of LT(H,r)\mathsf{LT}(H,r).

This is the sparse-limit analogue of the finite-pp bipartite lower-tail conjecture. The supplied text does not state a resolution; the result is known in cases covered by Sidorenko's conjecture.

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.