  The random assignment (or bipartite matching) problem studies the random
total cost A_n of the optimal assignment of each of n jobs to each of n
machines, where the costs of the n^2 possible job-machine matches has
exponential (mean 1) distribution. Mezard - Parisi (1987) used the replica
method from statistical physics to argue non-rigorously that EA_n converges to
zeta(2) = pi^2/6. Aldous (1992) identified the limit as the optimal solution of
a matching problem on an infinite tree. Continuing that approach, we construct
the optimal matching on the infinite tree. This yields a rigorous proof of the
zeta(2) limit and of the conjectured limit distribution of edge-costs and their
rank-orders in the optimal matching.
