Uniform-edge conjecture for the expected maximum matching in random bipartite graphs
Uniform-edge conjecture for the expected maximum matching in random bipartite graphs
Let be the complete bipartite graph with vertices on each side. A fractional bipartite matching is a collection of edge probabilities satisfying the vertex constraints and . Let be the random bipartite graph in which each edge appears independently with probability . Equivalently, let be a doubly stochastic matrix, with for corresponding vertices. Uniform-edge conjecture. The expected size of the maximum matching in is minimized when for every edge. Equivalently, for a random bipartite graph whose edge appears independently with probability , the expected maximum matching size is minimized when for all . The uniform instance is known to have expected maximum matching size , where and ; the conjecture asserts that this instance is worst among all fractional matchings in .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.