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

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

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

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

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

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

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

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

Эта статья по комбинаторике — заглушка . Вы можете помочь Википедии, расширив ее.

• в
• т
• е