Теорема Байка – Дейфта – Йоханссона

Теорема Байка -Дейфта-Йоханссона является результатом вероятностной комбинаторики . Он имеет дело с подпоследовательностями случайно равномерно нарисованной перестановки из множества $\{1,2,\dots ,N\}$. Теорема утверждает о распределении длины самой длинной возрастающей подпоследовательности в пределе. Теорема оказала влияние на теорию вероятностей, поскольку она связала КПЗ-универсальность с теорией случайных матриц .

Теорема была доказана в 1999 году Джинхо Байком , Перси Дейфтом и Куртом Йоханссоном .

Заявление

Для каждого $N\geq 1$ позволять $\pi _{N}$ быть равномерно выбранной перестановкой длины $N$. Позволять $l(\pi _{N})$ быть длиной самой длинной возрастающей подпоследовательности $\pi _{N}$.

Тогда у нас есть для каждого $x\in \mathbb {R}$ что

$\mathbb {P} \left({\frac {l(\pi _{N})-2{\sqrt {N}}}{N^{1/6}}}\leq x\right)\to F_{2}(x),\quad N\to \infty$

где $F_{2}(x)$ — распределение Трейси-Уидома гауссова унитарного ансамбля .

Литература

• Ромик, Дэн (2015). Удивительная математика самых длинных возрастающих подпоследовательностей . дои : 10.1017/CBO9781139872003 . ISBN  9781107075832 .
• Корвин, Иван (2018). «Комментарий Дэвида Олдоса и Перси Диакониса к книге «Самые длинные возрастающие подпоследовательности: от терпеливой сортировки к теореме Байка – Дейфта – Йоханссона» . Бюллетень Американского математического общества . 55 (3): 363–374. дои : 10.1090/bull/1623 .