Parisi's random assignment conjecture

For a complete bipartite graph Kn,nK_{n,n} with independent exponentially distributed edge appearance times of rate 11, let Lnn(n)L_{nn}(n) denote the length of a minimum nn-assignment, that is, a perfect matching, and let E(Lnn(n)){\rm E}(L_{nn}(n)) be its expected length. Parisi's conjecture.

E(Lnn(n))=1+14+19++1n2.{\rm E}(L_{nn}(n))=1+\frac{1}{4}+\frac{1}{9}+\dots+\frac{1}{n^2}.

Proposed by Parisi in 1998, this conjecture had been verified up to n=7n=7 at the time of the source; it was subsequently proved by Aldous, so the finite-nn 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

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.