Ajtai–Komlós–Tusnády theorem

The Ajtai–Komlós–Tusnády theorem is a result in probabilistic combinatorics. Given two random, distinct sets of points and in the unit square, the theorem gives then upper and lower bounds for the minimal total distance needed to match the points in one set to those in the other.
The theorem was proven in 1984 by the Hungarian mathematicians Miklós Ajtai, János Komlós, and Gábor Tusnády.

Statement

Let and be two independent random vectors, uniformly distributed over . Let denote the symmetric group, and the Euclidean norm on.
Then,
where are real constants.

Remarks

The notation means
The theorem implies that