OxTalks is Changing
Oxford Events, the new replacement for OxTalks, will launch on 16th March. From now until the launch of Oxford Events, new events cannot be published or edited on OxTalks while all existing records are migrated to the new platform. The existing OxTalks site will remain available to view during this period.
From 16th, Oxford Events will launch on a new website: events.ox.ac.uk, and event submissions will resume. You will need a Halo login to submit events. Full details are available on the Staff Gateway.
Minimum cost matching with random edge-costs
In a complete bipartite graph on $m$ by $n$ vertices, the $m\cdot n$ edges are assigned random costs, and we ask for the minimum total cost of a set of $k$ edges where no two share a vertex. This random model of combinatorial optimisation has been studied extensively as a test case for algorithms and as a toy model of a physical system.
It has been known since the 1990’s that taking the edge-costs to be independent mean 1 exponential permits explicit formulas for things like the expected minimum cost, the most famous case being the $\pi^2/6$ limit for the case $k=m=n$ (perfect matching).
In this talk I will show how the distribution, not just its expectation, can be computed explicitly and 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.
As time permits, I will describe how the results can be generalised to other optimisation problems like minimum 2-factor and minimum cover.
Date:
10 November 2025, 14:00
Venue:
Mathematical Institute, Woodstock Road OX2 6GG
Venue Details:
L5
Speaker:
Johan Wästlund (Chalmers University, Gothenburg)
Organising department:
Department of Statistics
Part of:
Probability seminar
Booking required?:
Not required
Audience:
Public
Editor:
James Martin
