Satz von Ajtai-Komlós-Tusnády

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 ${\displaystyle X=(X_{1},\dots ,X_{k})}${\displaystyle X=(X_{1},\dots ,X_{k})} und ${\displaystyle Y=(Y_{1},\dots ,Y_{k})}${\displaystyle Y=(Y_{1},\dots ,Y_{k})} im Einheitsquadrat ${\displaystyle [0,1]^{2}}${\displaystyle [0,1]^{2}}. 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]

Seien ${\displaystyle (X_{1},\dots ,X_{k})}${\displaystyle (X_{1},\dots ,X_{k})} und ${\displaystyle (Y_{1},\dots ,Y_{k})}${\displaystyle (Y_{1},\dots ,Y_{k})} zwei unabhängige Zufallsvektoren, welche der Gleichverteilung auf ${\displaystyle [0,1]^{2}}${\displaystyle [0,1]^{2}} folgen (d. h. ${\displaystyle X_{i}\in [0,1]^{2}}${\displaystyle X_{i}\in [0,1]^{2}}.) Sei ${\displaystyle S_{n}}${\displaystyle S_{n}} die symmetrische Gruppe und ${\displaystyle |\cdot |}${\displaystyle |\cdot |} die euklidische Norm in ${\displaystyle \mathbb {R} ^{2}}${\displaystyle \mathbb {R} ^{2}}.

Dann gilt

${\displaystyle \mathbb {P} \left(C_{1}{\sqrt {n\log n}}<\inf \limits _{\sigma \in S_{n}}\sum \limits _{k=1}^{n}|X_{k}-Y_{\sigma (k)}|<C_{2}{\sqrt {n\log n}}\right)=1-o(1),}${\displaystyle \mathbb {P} \left(C_{1}{\sqrt {n\log n}}<\inf \limits _{\sigma \in S_{n}}\sum \limits _{k=1}^{n}|X_{k}-Y_{\sigma (k)}|<C_{2}{\sqrt {n\log n}}\right)=1-o(1),}

wobei ${\displaystyle C_{1},C_{2}}${\displaystyle C_{1},C_{2}} reelle Konstanten sind.

• ${\displaystyle o(1)}${\displaystyle o(1)} bedeutet

${\displaystyle f(n)\in o(1)\iff \lim \limits _{n\to \infty }f(n)=0.}${\displaystyle f(n)\in o(1)\iff \lim \limits _{n\to \infty }f(n)=0.}     siehe Landau-Symbole.

• Der Satz sagt, dass

${\displaystyle \inf \limits _{\sigma \in S_{n}}{\frac {1}{n}}\sum \limits _{k=1}^{n}|X_{k}-Y_{\sigma (k)}|\sim {\sqrt {\frac {\log n}{n}}}}${\displaystyle \inf \limits _{\sigma \in S_{n}}{\frac {1}{n}}\sum \limits _{k=1}^{n}|X_{k}-Y_{\sigma (k)}|\sim {\sqrt {\frac {\log n}{n}}}}

mit hoher Wahrscheinlichkeit.

• Sergey Bobkov und Michel Ledoux: A simple Fourier analytic proof of the AKT optimal matching theorem. 2019 (englisch). 
• Ajtai, M., Komlos, Janos und Tusnády, G.: On optimal matchings. In: Combinatorica. Band 4, 1984, S. 259–264, doi:10.1007/BF02579135 (englisch). 
• Michel Talagrand: Matching theorems and empirical discrepancy computations using majorizing measures. In: Journal of the American Mathematical Society. Band 7, 1994, S. 455–537, doi:10.1090/S0894-0347-1994-1227476-X (englisch). 

1. ↑ Ajtai, M., Komlos, Janos und Tusnády, G.: On optimal matchings. In: Combinatorica. Band 4, 1984, S. 259–264, doi:10.1007/BF02579135 . 

• Satz (Stochastik)
• Kombinatorik