Analysis and Probability seminar

Abstract: Suppose that the edges of an $n$ by $n$ complete bipartite graph are assigned random costs, and we ask for the minimum total cost of a set of $n$ edges where no two share a vertex, so-called perfect matching.

It has been known since the 1990's that taking the edge-costs to be independent mean 1 exponential allows a surprisingly precise result about the expected minimum cost, which converges to $\pi^2/6$.

I will show how the distribution, not just the expectation, can be computed efficiently from a certain recursion. The recursion implies a Gaussian limit (after proper rescaling) of the cost of matching when a positive proportion of the vertices remain unmatched, although such a "central limit theorem" for perfect matching remains elusive.

If time permits, I will describe how the method can be applied to other optimization problems like the traveling salesman.