Concentration of the cost of a random matching problem

• Let Mn be the minimum cost of a perfect matching on a complete graph on n vertices whose edges are assigned independent exponential costs. It follows from work of D. Aldous that Mn converges in probability to π2/12. This was earlier conjectured by M. Mézard and G. Parisi. We establish the more precise result that E | Mn – π2/12| = O(n-1/2).

Subject headings

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Keyword

MATHEMATICS

MATEMATIK

Publication and Content Type

vet (subject category)

ovr (subject category)