Uniform-edge conjecture for the expected maximum matching in random bipartite graphs

Let Kn,nK_{n,n} be the complete bipartite graph with nn vertices on each side. A fractional bipartite matching is a collection of edge probabilities x=(xuv)x=(x_{uv}) satisfying the vertex constraints vxuv=1\sum_v x_{uv}=1 and uxuv=1\sum_u x_{uv}=1. Let R(x)R(x) be the random bipartite graph in which each edge (u,v)(u,v) appears independently with probability xuvx_{uv}. Equivalently, let A=(aij)A=(a_{ij}) be a doubly stochastic n×nn\times n matrix, with xuv=aijx_{uv}=a_{ij} for corresponding vertices. Uniform-edge conjecture. The expected size of the maximum matching in R(x)R(x) is minimized when xuv=1/nx_{uv}=1/n for every edge. Equivalently, for a random bipartite graph whose edge (i,j)(i,j) appears independently with probability aija_{ij}, the expected maximum matching size is minimized when aij=1/na_{ij}=1/n for all (i,j)(i,j). The uniform instance is known to have expected maximum matching size (γ+o(1))n(\gamma+o(1))n, where γ=2(1λ)λ2\gamma=2(1-\lambda)-\lambda^2 and λ=eλ\lambda=e^{-\lambda}; the conjecture asserts that this instance is worst among all fractional matchings in Kn,nK_{n,n}.

Sources & referencesView supporting material

Primary source

Pranav Nuti and Jan Vondrák, “Towards an Optimal Contention Resolution Scheme for Matchings”, arXiv:2211.03599 (2024).

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.