Satz von Ajtai-Komlós-Tusnády
Satz aus der probabilistischen Kombinatorik / aus Wikipedia, der freien encyclopedia
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.[1]