Гипотеза Стэнли–Вильфа

Гипотеза Стэнли–Вильфа , сформулированная независимо Ричардом П. Стэнли и Гербертом Вильфом в конце 1980-х годов, утверждает, что скорость роста каждого класса собственных перестановок является единично экспоненциальной . Она была доказана Адамом Маркусом и Габором Тардосом  (2004) и больше не является гипотезой. Маркус и Тардос на самом деле доказали другую гипотезу, выдвинутую Золтаном Фюреди и Петером Хайналом (1992), которая, как было показано Клазаром (2000), подразумевает гипотезу Стэнли–Вильфа.

Гипотеза Стэнли–Вилфа утверждает, что для каждой перестановки β существует константа C такая, что число | S _n ( β )| перестановок длины n , которые избегают β как шаблона перестановки, не превышает C ⁿ . Как заметил Арратия (1999), это эквивалентно сходимости предела

${\displaystyle \lim _{n\to \infty }{\sqrt[{n}]{|S_{n}(\beta )|}}.}$

Верхняя граница, данная Маркусом и Тардосом для C , экспоненциальна по длине β . Более сильная гипотеза Арратии (1999) утверждала, что можно было бы взять C равным ( k − 1) ² , где k обозначает длину β , но эта гипотеза была опровергнута для перестановки β = 4231 Альбертом и др. (2006). Действительно, Фокс (2013) показал, что C на самом деле экспоненциальна по k для почти всех перестановок.

Скорость роста (или предел Стэнли–Уилфа) класса перестановок определяется как

${\displaystyle \limsup _{n\to \infty }{\sqrt[{n}]{a_{n}}},}$

где a _n обозначает число перестановок длины n в классе. Очевидно, что не каждое положительное действительное число может быть темпом роста класса перестановок, независимо от того, определяется ли он одним запрещенным шаблоном или набором запрещенных шаблонов. Например, числа строго между 0 и 1 не могут быть темпами роста классов перестановок.

Кайзер и Клазар (2002) доказали, что если число перестановок в классе длины n всегда меньше n- го числа Фибоначчи , то перечисление класса в конечном итоге становится полиномиальным. Следовательно, числа строго между 1 и золотым сечением также не могут быть темпами роста классов перестановок. Кайзер и Клазар продолжили устанавливать все возможные константы роста класса перестановок ниже 2; это наибольшие действительные корни полиномов

${\displaystyle x^{k+1}-2x^{k}+1}$

для целого числа k  ≥ 2. Это показывает, что 2 является наименьшей точкой накопления темпов роста классов перестановок.

Позднее Ваттер (2011) расширил характеристику темпов роста классов перестановок до определенного алгебраического числа κ≈2,20. Из этой характеристики следует, что κ является наименьшей точкой накопления точек накопления темпов роста и что все темпы роста до κ являются алгебраическими числами. Ваттер (2019) установил, что существует алгебраическое число ξ≈2,31 такое, что существует несчетное множество темпов роста в каждой окрестности ξ, но только счетное множество темпов роста ниже него. Пантоне и Ваттер (2020) охарактеризовали (счетное множество) темпов роста ниже ξ, все из которых также являются алгебраическими числами. Их результаты также подразумевают, что в множестве всех темпов роста классов перестановок ξ является наименьшей точкой накопления сверху.

В другом направлении, Vatter (2010) доказал, что каждое действительное число не менее 2,49 является скоростью роста класса перестановок. Этот результат был позже улучшен Bevan (2018), который доказал, что каждое действительное число не менее 2,36 является скоростью роста класса перестановок.

• Перечисления конкретных классов перестановок для темпов роста конкретных классов перестановок.

• Альберт, Майкл Х.; Элдер, Мюррей; Рехницер, Эндрю; Уэсткотт, П.; Заброцкий, Майк (2006), «О пределе Стэнли–Уилфа для перестановок, избегающих 4231, и гипотезе Арратии», Advances in Applied Mathematics , 36 (2): 96–105, doi : 10.1016/j.aam.2005.05.007 , hdl : 10453/98769 , MR  2199982.
• Арратия, Ричард (1999), «О гипотезе Стэнли–Вильфа для числа перестановок, избегающих заданного шаблона», Электронный журнал комбинаторики , 6 : N1, doi : 10.37236/1477 , MR  1710623.
• Беван, Дэвид (2018) [2014], «Интервалы темпов роста класса перестановок», Combinatorica , 38 (2): 279–303, arXiv : 1410.3679 , Bibcode : 2014arXiv1410.3679B, doi : 10.1007/s00493-016-3349-2, S2CID  254031975.
• Фокс, Джейкоб (2013), Пределы Стэнли–Уилфа обычно экспоненциальны , arXiv : 1310.8378 , Bibcode : 2013arXiv1310.8378F.
• Фюреди, Золтан ; Хайнал, Питер (1992), «Теория матриц Давенпорта – Шинзеля», Discrete Mathematics , 103 (3): 233–251, doi : 10.1016/0012-365X(92)90316-8 , MR  1171777.
• Кайзер, Томаш; Клазар, Мартин (март 2002 г.), «О темпах роста замкнутых классов перестановок», Электронный журнал комбинаторики , 9 (2): Исследовательская статья 10, 20, MR  2028280.
• Клазар, Мартин (2000), «Гипотеза Фюреди–Хайнала влечет гипотезу Стэнли–Вильфа», Формальные степенные ряды и алгебраическая комбинаторика (Москва, 2000) , Springer, стр. 250–255, MR  1798218.
• Клазар, Мартин (2010), «Некоторые общие результаты комбинаторного перечисления», Шаблоны перестановок , London Math. Soc. Lecture Note Ser., т. 376, Кембридж: Cambridge Univ. Press, стр. 3–40, doi : 10.1017/CBO9780511902499.002, ISBN 978-0-521-72834-8, г-н  2732822.
• Маркус, Адам ; Тардос, Габор (2004), «Исключенные матрицы перестановок и гипотеза Стэнли–Вильфа», Журнал комбинаторной теории , Серия A, 107 (1): 153–160, doi : 10.1016/j.jcta.2004.04.002 , MR  2063960.
• Pantone, Jay; Vatter, Vincent (2020), «Темпы роста классов перестановок: категоризация до порога несчетности», Israel Journal of Mathematics , 236 (1): 1–43, arXiv : 1605.04289 , doi : 10.1007/s11856-020-1964-5 , MR  4093880.
• Vatter, Vincent (2019), «Темпы роста классов перестановок: от счетных к несчетным», Proc. London Math. Soc. , Series 3, 119 (4): 960–997, arXiv : 1605.04297 , doi : 10.1112/plms.12250, MR  3964825, S2CID  118595642.
• Vatter, Vincent (2010), «Классы перестановок для каждой скорости роста выше 2,48188», Mathematika , 56 (1): 182–192, arXiv : 0807.2815 , doi : 10.1112/S0025579309000503, MR  2604993, S2CID  228723.
• Vatter, Vincent (2011), «Малые классы перестановок», Proc. London Math. Soc. , Series 3, 103 (5): 879–921, arXiv : 0712.4006 , doi : 10.1112/plms/pdr017, MR  2852292, S2CID  16116435.

• Как Адам Маркус и Габор Тардос разделили и победили гипотезу Стэнли–Вильфа — Дорон Зейлбергер .
• Вайсштейн, Эрик В. «Гипотеза Стэнли–Вильфа». MathWorld .