Der Satz von Ajtai-Komlós-Tusnády (auch AKT optimal matching theorem) ist ein Satz aus der probabilistischen Kombinatorik. Gegeben sind zwei zufällige, verschiedene Mengen von Punkten und im Einheitsquadrat . Dann macht der Satz eine Aussage über die obere und untere Schranke der kleinsten Summe der Distanzen der Punkte.

Der Satz wurde 1984 von den ungarischen Mathematikern Miklós Ajtai, János Komlós und Gábor Tusnády bewiesen.

Aussage Seien und zwei unabhängige Zufallsvektoren, welche der Gleichverteilung auf folgen (d. h. .) Sei die symmetrische Gruppe und die euklidische Norm in .

Dann gilt

wobei reelle Konstanten sind.

Erläuterungen bedeutet     siehe Landau-Symbole.

Der Satz sagt, dass

mit hoher Wahrscheinlichkeit.

Literatur

Einzelnachweise

Ajtai-Komlos-Tusnady, Satz von Kategorie:Kombinatorik