Parisi's random assignment conjecture
Parisi's random assignment conjecture
For a complete bipartite graph with independent exponentially distributed edge appearance times of rate , let denote the length of a minimum -assignment, that is, a perfect matching, and let be its expected length. Parisi's conjecture.
Proposed by Parisi in 1998, this conjecture had been verified up to at the time of the source; it was subsequently proved by Aldous, so the finite- expectation is exactly the stated sum.
Sources & referencesView supporting material
Primary source
Henrik Eriksson, Kimmo Eriksson and Jonas Sjostrand, “Exact expectations for random graphs and assignments”, arXiv:math/0411199 (2004).
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.