Шаблон перестановки - Permutation pattern

В комбинаторная математика и теоретическая информатика, а шаблон перестановки является подстановкой более длинного перестановка. Любая перестановка может быть записана в однострочная запись как последовательность цифр, представляющих результат применения перестановки к последовательности цифр 123 ...; например, последовательность цифр 213 представляет собой перестановку трех элементов, которая меняет местами элементы 1 и 2. Если π и σ представляют собой две перестановки, представленные таким образом (эти имена переменных являются стандартными для перестановок и не связаны с числом число Пи ), то π называется содержать σ как шаблон если некоторая подпоследовательность цифр π имеет тот же относительный порядок, что и все цифры σ.

Например, перестановка π содержит образец 213, если π состоит из трех цифр. Икс, у, и z которые появляются внутри π в порядке Икс...у...z но чьи значения упорядочены как у < Икс < z, то же, что и порядок значений в перестановке 213. Перестановка 32415 на пяти элементах содержит 213 в качестве шаблона несколькими различными способами: 3 ·· 15, ·· 415, 32 ·· 5, 324 ·· и · 2 · 15 образуют тройки цифр с тем же порядком, что и 213. Каждая из подпоследовательностей 315, 415, 325, 324 и 215 называется копия пример, или же вхождение выкройки. Тот факт, что π содержит σ, более кратко записывается как σ ≤ π. Если перестановка π не содержит шаблона σ, то говорят, что π избегать σ. Перестановка 51342 позволяет избежать 213; он имеет 10 подпоследовательностей из трех цифр, но ни одна из этих 10 подпоследовательностей не имеет того же порядка, что и 213.

Первые результаты

Можно сделать вывод, что Перси МакМахон  (1915 ) был первым, кто доказал результат в этой области, изучая «решеточные перестановки».^[1] В частности, Мак-Магон показывает, что перестановки, которые можно разделить на две убывающие подпоследовательности (т. Е. Перестановки, избегающие 123), подсчитываются Каталонские числа.^[2]

Еще один ранний знаковый результат в этой области - Теорема Эрдеша – Секереса; на языке шаблонов перестановок теорема утверждает, что для любых натуральных чисел а и б каждая перестановка длины не менее ${ Displaystyle (а-1) (б-1) +1}$ должен содержать либо образец ${ Displaystyle 1,2,3, точки, а}$ или узор ${ displaystyle b, b-1, dots, 2,1}$.

Истоки информатики

Изучение паттернов перестановок всерьез началось с Дональд Кнут рассмотрение стековая сортировка в 1968 г.^[3] Кнут показал, что перестановка π может быть отсортирована куча тогда и только тогда, когда π избегает 231, и что сортированные по стеку перестановки нумеруются Каталонские числа.^[4] Кнут также поднял вопросы о сортировке с помощью дек. В частности, вопрос Кнута о том, сколько перестановок п элементы можно получить с помощью двухстороннего остаётся открытым.^[5] Вскоре после этого, Роберт Тарджан  (1972 ) исследовал сортировку по сетям стопок,^[6] пока Воан Пратт  (1973 ) показал, что перестановка π может быть отсортирована по двухсторонней очереди тогда и только тогда, когда для всех k, π избегает 5,2,7,4, ..., 4k+1,4k−2,3,4k, 1 и 5,2,7,4, ..., 4k+3,4k,1,4k+2,3, и любая перестановка, которая может быть получена из любого из них, заменяя последние два элемента местами 1 и 2.^[7] Поскольку этот набор перестановок бесконечен (фактически, это первый опубликованный пример бесконечного антицепь перестановок), не сразу понятно, сколько времени потребуется, чтобы решить, может ли перестановка быть отсортирована по двухсторонней очереди. Розенштиль и Тарьян (1984) позже представил линейный (по длине π) алгоритм времени, который определяет, можно ли отсортировать π по двухсторонней очереди.^[8]

В своей статье Пратт заметил, что этот порядок паттернов перестановок «кажется единственным частичным порядком перестановок, который возникает простым и естественным образом», и в заключение отмечает, что «с абстрактной точки зрения» порядок паттернов перестановок «является даже интереснее, чем описываемые нами сети ».^[7]

Перечислительное происхождение

Важной целью при изучении паттернов перестановок является перечисление перестановок, избегая фиксированной (и обычно короткой) перестановки или набора перестановок. Позволять Средний_п(B) обозначим множество перестановок длины п которые избегают всех перестановок в наборе B (в случае B одноэлементный, скажем β, сокращение Средний_п(β) используется вместо). Как отмечалось выше, Мак-Магон и Кнут показали, что |Средний_п(123)| = |Средний_п(231)| = C_п, то пй каталонский номер. Таким образом, они изоморфны комбинаторные классы.

Симион и Шмидт (1985) был первым документом, посвященным исключительно перечислению. Среди других результатов Симион и Шмидт насчитали четные и нечетные перестановки избегая шаблона длины три, считая перестановки, избегая два выкройки длины три, и дал первое биективное доказательство того, что перестановки, избегающие 123 и 231, равны.^[9] После их статьи было дано много других биекций, см. Клаэссон и Китаев (2008) для опроса.^[10]

В общем, если |Средний_п(β) | = |Средний_п(σ) | для всех п, то β и σ называются Эквивалент Уилфа. Многие эквивалентности Вильфа проистекают из тривиального факта, что |Средний_п(β) | = |Средний_п(β⁻¹)| = |Средний_п(β^rev) | для всех п, где β^-1 обозначает обратный β и β^rev обозначает обратное β. (Эти две операции генерируют Группа диэдра D₈ с естественным действием на матрицы перестановок.) Однако есть также многочисленные примеры нетривиальных эквивалентностей Уилфа (например, между 123 и 231):

• Станкова (1994) доказал, что перестановки 1342 и 2413 эквивалентны Вильфу.^[11]
• Станкова и Запад (2002) доказал, что для любой перестановки β перестановки 231 ⊕ β и 312 ⊕ β эквивалентны Вильфу, где ⊕ обозначает прямая сумма операция.^[12]
• Бакелин, Запад и Синь (2007) доказал, что для любой перестановки β и любого натурального числа м, перестановки 12 ..м ⊕ β и м...21 ⊕ β являются Wilf-эквивалентными.^[13]

Из этих двух эквивалентностей Вильфа и обратной и обратной симметрии следует, что существуют три различные последовательности |Средний_п(β) | где β имеет длину четыре:

В конце 1980-х гг. Ричард Стэнли и Герберт Уилф предположил, что для каждой перестановки β существует некоторая постоянная K такой, что |Средний_п(β) | < K^п. Это было известно как Гипотеза Стэнли – Уилфа пока это не было доказано Адам Маркус и Габор Тардос.^[16]

Закрытые классы

А закрытый класс, также известный как класс шаблона, класс перестановки, или просто учебный класс перестановок - это сбивать в порядке перестановки. Каждый класс может быть определен минимальными перестановками, которые не лежат внутри него, его основа. Таким образом, базис для перестановок, сортируемых по стеку, равен {231}, в то время как базис для перестановок, сортируемых по стеку, бесконечен. В производящая функция для класса Σ x^{| π |} где сумма берется по всем перестановкам π в классе.

Функция Мёбиуса

Поскольку набор перестановок согласно порядку включения образует посеть естественно спросить о его Функция Мёбиуса, цель, впервые явно представленная Уилф (2002).^[17]Цель таких исследований - найти формулу для функции Мёбиуса интервала [σ, π] в шаблоне перестановки poset, которая более эффективна, чем наивное рекурсивное определение. Первый такой результат был установлен Саган и Ваттер (2006), который дал формулу функции Мёбиуса отрезка слоистые перестановки.^[18]Потом, Бурштейн и др. (2011) обобщил этот результат на интервалы разделимые перестановки.^[19]

Известно, что асимптотически не менее 39,95% всех перестановок π длины п удовлетворяют условию μ (1, π) = 0 (то есть главная функция Мёбиуса равна нулю)^[20], но для каждого п существуют перестановки π такие, что μ (1, π) является экспоненциальной функцией от п^[21].

Вычислительная сложность

Учитывая перестановку ${ Displaystyle тау}$ (называется текст) длины ${ displaystyle n}$ и еще одна перестановка ${ displaystyle pi}$ длины ${ displaystyle k}$ (называется шаблон), сопоставление с образцом перестановки (PPM) проблема спрашивает, есть ли ${ displaystyle pi}$ содержится в ${ Displaystyle тау}$. Когда оба ${ displaystyle n}$ и ${ displaystyle k}$ рассматриваются как переменные, проблема, как известно, НП-полный, а задача подсчета количества таких совпадений - # P-complete.^[22] Однако PPM можно решить за линейное время когда k является константой. Действительно, Гиймо и Маркс^[23] показал, что PPM можно решить вовремя ${ Displaystyle 2 ^ {О (к ^ {2} журнал к)} CDOT п}$, что означает, что это управляемый с фиксированными параметрами относительно ${ displaystyle k}$.

Согласно обзору Брунера и Лакнера, существует несколько вариантов проблемы PPM.^[24] Например, если требуется, чтобы совпадение состояло из смежных записей, проблема может быть решена за полиномиальное время.^[25]

Другой вариант - когда и шаблон, и текст ограничены правильным классом перестановки. ${ displaystyle { mathcal {C}}}$, в этом случае проблема называется ${ displaystyle { mathcal {C}}}$-PPM. Например, Guillemot и Vialette^[26] показало, что ${ displaystyle { mbox {Av}} (321)}$-PPM может быть решена в ${ Displaystyle О (к ^ {2} п ^ {6})}$ время. Альберт, Лакнер, Лакнер и Ваттер^[27] позже снизил это до ${ Displaystyle О (кн)}$ и показал, что такая же оценка верна для класса перестановки с перекосом. Они также спросили, есть ли ${ displaystyle { mathcal {C}}}$-Проблема PPM может быть решена за полиномиальное время для каждого фиксированного собственного класса перестановок ${ displaystyle { mathcal {C}}}$.

Плотность упаковки

Перестановка π называется β-оптимальный если никакая перестановка той же длины, что и π, не имеет большего количества копий β. В своем выступлении на заседании SIAM по дискретной математике в 1992 году Уилф определил плотность упаковки перестановки β длины k в качестве

${ displaystyle lim _ {n rightarrow infty} { frac {{ text {количество копий}} beta { text {in a}} beta { text {-оптимальная перестановка длины}} n} { displaystyle {n choose k}}}.}$

Неопубликованный аргумент Фред Гэлвин показывает, что количество внутри этого предел не увеличивается для п ≥ k, так что предел существует. Когда β является монотонным, его плотность упаковки, очевидно, равна 1, а плотности упаковки инвариантны относительно группы симметрий, порождаемых обратной и обратной, так что для перестановок длины три существует только одна нетривиальная плотность упаковки. Уолтер Стромквист (не опубликовано) разрешил этот случай, показав, что плотность упаковки 132 равна 2.√3 - 3, примерно 0,46410.

Для перестановок β длины четыре необходимо рассмотреть (в силу симметрии) семь случаев:

Для трех неизвестных перестановок существуют оценки и предположения. Цена (1997) использовал алгоритм аппроксимации, который предполагает, что плотность упаковки 1324 составляет около 0,244.^[28] Биржан Баткеев (неопубликовано) построил семейство перестановок, показывающих, что плотность упаковки 1342, по крайней мере, является произведением плотностей упаковки 132 и 1432, приблизительно 0,19658. Предполагается, что это точная плотность упаковки 1342. Престутти и Стромквист (2010) обеспечили нижнюю границу плотности упаковки 2413. Эта нижняя граница, которая может быть выражена через интеграл, составляет приблизительно 0,10474 и предположительно является истинной плотностью упаковки.^[30]

Суперштейнеры

А k-суперпаттерн это перестановка, содержащая все перестановки длины k. Например, 25314 - это 3-супершаттерн, потому что он содержит все 6 перестановок длины 3. Известно, что k-суперпаттерны должны иметь длину не менее k²/е², куда е ≈ 2,71828 составляет Число Эйлера,^[31] и что существуют k-супершаблоны длины ⌈ (k² + 1)/2⌉.^[32]Предполагается, что эта верхняя граница является наилучшей с точностью до членов нижнего порядка.^[33]

Обобщения

Есть несколько способов обобщения понятия «паттерн». Например, винкулярный узор представляет собой перестановку, содержащую дефисы, указывающие на записи, которые не должны появляться последовательно (в обычном определении шаблона, никакие записи не должны появляться последовательно). Например, перестановка 314265 имеет две копии штрихового рисунка 2-31-4, заданного записями 3426 и 3425. Для штрихового рисунка β и любой перестановки π мы пишем β (π) для количества копий β. в π. Таким образом, число инверсий в π равно 2-1 (π), а количество спусков - 21 (π). В дальнейшем количество долины в π равно 213 (π) + 312 (π), а количество вершины равно 231 (π) + 132 (π). Эти шаблоны были введены Бабсон и Штайнгримссон (2000), которые показали, что почти все известные Махонская статистика можно выразить в терминах винкулярных перестановок.^[34] Например, Основной индекс числа π равно 1-32 (π) + 2-31 (π) + 3-21 (π) + 21 (π).

Другое обобщение - это полосатый узор, в котором некоторые записи запрещены. Для π, чтобы избежать шаблона с перемычкой, β означает, что каждый набор записей π, которые формируют копию записей без перемычки β, может быть расширен, чтобы сформировать копию всех записей β. Запад (1993) представил эти типы шаблонов в своем исследовании перестановок, которые можно было отсортировать, дважды пропустив их через стек.^[35] (Обратите внимание, что определение Уэста сортировки дважды в стеке не то же самое, что сортировка с двумя последовательными стопками.) Другой пример шаблонов с перемычками встречается в работе Буске-Мелу и Батлер (2007), который показал, что Сорт Шуберта соответствует π, является локально факториал тогда и только тогда, когда π избегает 1324 и 21354.^[36]

Рекомендации

внешняя ссылка

Конференция по шаблонам перестановок была проводится ежегодно с 2003 г.:

1. Паттерны перестановки 2003, 10–14 февраля 2003 г., г. Университет Отаго, Данидин, Новая Зеландия.
2. Паттерны перестановки 2004, 5–9 июля 2004 г., г. Университет-колледж Маласпины, Нанаймо, Британская Колумбия, Канада.
3. Паттерны перестановки 2005, 7–11 марта 2005 г., г. Университет Флориды, Гейнсвилл, Флорида, США.
4. Паттерны перестановки 2006, 12–16 июня 2006 г., г. Рейкьявикский университет, Рейкьявик, Исландия.
5. Паттерны перестановки 2007, 11–15 июня 2007 г., г. Сент-Эндрюсский университет, Сент-Эндрюс, Шотландия.
6. Паттерны перестановки 2008, 16–20 июня 2008 г., г. Университет Отаго, Данидин, Новая Зеландия.
7. Паттерны перестановки 2009, 13–17 июля 2009 г., г. Università di Firenze, Флоренция, Италия.
8. Паттерны перестановки 2010, 9–13 августа 2010 г., г. Дартмутский колледж, Ганновер, Нью-Гэмпшир, США.
9. Паттерны перестановки 2011, 20–24 июня 2011 г., г. Калифорнийский политехнический государственный университет, Сан-Луис-Обиспо, Калифорния, США.
10. Паттерны перестановки 2012, 11–15 июня 2012 г., г. Стратклайдский университет, Глазго, Шотландия.
11. Паттерны перестановки 2013, 1–5 июля 2013 г., г. Университет Парижа Дидро, Париж, Франция.
12. Шаблоны перестановок 2014, 7–11 июля 2014 г., г. Государственный университет Восточного Теннесси, Джонсон-Сити, Теннесси, США.
13. Паттерны перестановки 2015, 15–19 июня 2015 г., г. Дом Де Моргана, Лондон, Англия.
14. Паттерны перестановки 2016, 27 июня - 1 июля 2016 г., Университет Говарда, Вашингтон, округ Колумбия, США.
15. Шаблоны перестановок 2017, 26–30 июня 2017 г., г. Рейкьявикский университет, Рейкьявик, Исландия.
16. Шаблоны перестановок 2018, 9–13 июля 2018 г., г. Дартмутский колледж, Ганновер, Нью-Гэмпшир, США.
17. Паттерны перестановки 2019, 17–21 июня 2019 г., г. Universität Zürich, Цюрих, Швейцария.
18. Виртуальная мастерская по шаблонам перестановок 2020, 30 июня - 1 июля 2020 г., организатор Университет Вальпараисо, Вальпараисо, Индиана, США.

Американское математическое общество Специальные сессии по шаблонам в перестановках были проведены на следующих встречах:

• Осеннее восточное секционное собрание, 22–23 сентября 2012 г., г. Рочестерский технологический институт, Рочестер, штат Нью-Йорк.
• Совместные встречи по математике, 12 января 2013 г., Сан-Диего, Калифорния.
• Центральное осеннее секционное собрание, 20–21 сентября 2014 г., г. Университет Висконсин-О-Клэр, Eau Claire, WI.
• Весеннее восточное секционное собрание, 7–8 марта 2015 г., Джорджтаунский университет, Вашингтон, округ Колумбия.

Встречи с другими шаблонами перестановки:

• Мастер-класс по шаблонам перестановок, 29 мая - 3 июня 2005 г., Хайфский университет, Хайфа, Израиль.

Другие ссылки:

• PermLab: программа для шаблонов перестановок, поддерживается Майкл Альберт.
• База данных избегания паттернов перестановки, поддерживается Бриджит Теннер.