---
tag: N4FHGY5J15
kind: statement
role: proposition
name: Ajtai–Komlós–Tusnády theorem
aliases: [akt-optimal-matching-theorem]
sources:
  - wikipedia: en:79806570@r1373512872
    locator: Ajtai–Komlós–Tusnády theorem
    note: adopted
    mention: wikipedia://en/79806570
    sections: [Statement]
same_as:
  wikidata: Q117283062
  wikipedia: Ajtai–Komlós–Tusnády theorem
inventory: [K1878K0W3W]
---

## Statement

The **Ajtai–Komlós–Tusnády theorem** (also known as the **AKT optimal matching theorem**) is a result in probabilistic combinatorics. Given two random, distinct sets of points $X=(X_1,\dots,X_k)$ and $Y=(Y_1,\dots,Y_k)$ in the unit square $[0,1]^2$, the theorem gives upper and lower bounds for the minimal total distance needed to match the points in one set to those in the other.