Гипотеза Стэнли–Вильфа , сформулированная независимо Ричардом П. Стэнли и Гербертом Вильфом в конце 1980-х годов, утверждает, что скорость роста каждого класса собственных перестановок является единично экспоненциальной . Она была доказана Адамом Маркусом и Габором Тардосом (2004) и больше не является гипотезой. Маркус и Тардос на самом деле доказали другую гипотезу, выдвинутую Золтаном Фюреди и Петером Хайналом (1992), которая, как было показано Клазаром (2000), подразумевает гипотезу Стэнли–Вильфа.
Гипотеза Стэнли–Вилфа утверждает, что для каждой перестановки β существует константа C такая, что число | S n ( β )| перестановок длины n , которые избегают β как шаблона перестановки, не превышает C n . Как заметил Арратия (1999), это эквивалентно сходимости предела
Верхняя граница, данная Маркусом и Тардосом для C , экспоненциальна по длине β . Более сильная гипотеза Арратии (1999) утверждала, что можно было бы взять C равным ( k − 1) 2 , где k обозначает длину β , но эта гипотеза была опровергнута для перестановки β = 4231 Альбертом и др. (2006). Действительно, Фокс (2013) показал, что C на самом деле экспоненциальна по k для почти всех перестановок.
Скорость роста (или предел Стэнли–Уилфа) класса перестановок определяется как
где a n обозначает число перестановок длины n в классе. Очевидно, что не каждое положительное действительное число может быть темпом роста класса перестановок, независимо от того, определяется ли он одним запрещенным шаблоном или набором запрещенных шаблонов. Например, числа строго между 0 и 1 не могут быть темпами роста классов перестановок.
Кайзер и Клазар (2002) доказали, что если число перестановок в классе длины n всегда меньше n- го числа Фибоначчи , то перечисление класса в конечном итоге становится полиномиальным. Следовательно, числа строго между 1 и золотым сечением также не могут быть темпами роста классов перестановок. Кайзер и Клазар продолжили устанавливать все возможные константы роста класса перестановок ниже 2; это наибольшие действительные корни полиномов
для целого числа k ≥ 2. Это показывает, что 2 является наименьшей точкой накопления темпов роста классов перестановок.
Позднее Ваттер (2011) расширил характеристику темпов роста классов перестановок до определенного алгебраического числа κ≈2,20. Из этой характеристики следует, что κ является наименьшей точкой накопления точек накопления темпов роста и что все темпы роста до κ являются алгебраическими числами. Ваттер (2019) установил, что существует алгебраическое число ξ≈2,31 такое, что существует несчетное множество темпов роста в каждой окрестности ξ, но только счетное множество темпов роста ниже него. Пантоне и Ваттер (2020) охарактеризовали (счетное множество) темпов роста ниже ξ, все из которых также являются алгебраическими числами. Их результаты также подразумевают, что в множестве всех темпов роста классов перестановок ξ является наименьшей точкой накопления сверху.
В другом направлении, Vatter (2010) доказал, что каждое действительное число не менее 2,49 является скоростью роста класса перестановок. Этот результат был позже улучшен Bevan (2018), который доказал, что каждое действительное число не менее 2,36 является скоростью роста класса перестановок.
![{\displaystyle \lim _{n\to \infty }{\sqrt[{n}]{|S_{n}(\beta )|}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42dd51a1331a4c746b742c30fa46c513e81d8c23)
![{\displaystyle \limsup _{n\to \infty }{\sqrt[{n}]{a_{n}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d0bc3311a311daa7da061b46b1303ff89ad2080)
