stringtranslate.com

Модель перестановки

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

Например, перестановка π содержит шаблон 213 всякий раз, когда π имеет три записи x , y и z , которые появляются в π в порядке x ... y ... z, но чьи значения упорядочены как y  <  x  <  z , так же, как порядок значений в перестановке 213.

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

Если перестановка π не содержит шаблон σ, то говорят, что π избегает σ. Перестановка 51342 избегает 213; она имеет десять подпоследовательностей из трех записей, но ни одна из этих десяти подпоследовательностей не имеет того же порядка, что и 213.

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

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

Другим ранним знаменательным результатом в этой области является теорема Эрдёша–Секереша ; на языке шаблонов перестановок теорема утверждает, что для любых положительных целых чисел a и b каждая перестановка длины не менее должна содержать либо шаблон , либо шаблон .

Истоки компьютерной науки

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

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

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

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

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

В общем случае, если |Av n ( β )| = |Av n ( σ )| для всех n , то β и σ называются эквивалентными по Вильфу . Многие эквивалентности Вильфа вытекают из тривиального факта, что |Av n ( β )| = |Av n ( β −1 )| = |Av n ( β rev )| для всех n , где β −1 обозначает инверсию β , а β rev обозначает обратную β . (Эти две операции порождают диэдральную группу D 8 с естественным действием на матрицах перестановок .) Однако существуют также многочисленные примеры нетривиальных эквивалентностей Вильфа (например, между 123 и 231 ):

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

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

Закрытые занятия

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

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

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

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

Сложность вычислений

При наличии перестановки (называемой текстом ) длины и другой перестановки длины (называемой шаблоном ), задача сопоставления шаблонов перестановок (PPM) спрашивает, содержится ли в . Когда и рассматриваются как переменные, известно, что задача является NP-полной , а задача подсчета количества таких совпадений является #P-полной . [22] Однако PPM может быть решена за линейное время , когда k является константой. Действительно, Гийемо и Маркс [23] показали, что PPM может быть решена за время , что означает, что она является фиксированно параметрически разрешимой относительно .

Существует несколько вариантов задачи PPM, как было рассмотрено Брунером и Лакнером. [24] Например, если требуется, чтобы соответствие состояло из смежных записей, то задача может быть решена за полиномиальное время. [25] Другой естественный вариант получается, когда шаблон ограничен надлежащим классом перестановок . Эта задача известна как -Pattern PPM, и было показано, что она разрешима за полиномиальное время для разделимых перестановок . [22] Позднее Елинек и Кинчл [26] полностью решили сложность -Pattern PPM, показав, что она разрешима за полиномиальное время, когда равно одному из 1, 12, 21, 132, 231, 312 или 213, и является NP-полной в противном случае.

Другой вариант — когда и шаблон, и текст ограничены собственным классом перестановок , в этом случае проблема называется -PPM. Например, Гийемо и Виалетт [27] показали, что -PPM может быть решена за время. Альберт , Лакнер, Лакнер и Ваттер [28] позже понизили это до и показали, что та же граница справедлива для класса перекошенных слитых перестановок . Они также спросили, может ли проблема -PPM быть решена за полиномиальное время для каждого фиксированного собственного класса перестановок . На этот вопрос отрицательно ответили Елинек и Кинчл, которые показали, что -PPM на самом деле является NP-полной. [26] Позднее Елинек, Оплер и Пекарек [29] показали, что -PPM является NP-полным для любого числа длины не менее 4, не симметричного одному из чисел 3412, 3142, 4213, 4123 или 41352.

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

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

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

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

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

Суперпаттерны

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

Обобщения

Тип шаблона, определенный выше, в котором записи не обязательно должны появляться последовательно, называется классическим (перестановочным) шаблоном. Если записи должны быть последовательными, то шаблон называется последовательным шаблоном .

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

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

Ссылки

  1. ^ MacMahon, Percy A. (1915), Комбинаторный анализ , Лондон: Cambridge University Press, Том I, Раздел III, Глава V.
  2. ↑ MacMahon (1915), пункты 97 и 98.
  3. ^ Кнут, Дональд Э. (1968), Искусство программирования компьютеров. Том 1 , Бостон: Addison-Wesley, ISBN 0-201-89683-4, MR  0286317, OCLC  155842391.
  4. ^ Кнут (1968), Раздел 2.2.1, Упражнения 4 и 5.
  5. ↑ Кнут (1968), раздел 2.2.1, упражнение 13, рейтинг M49 в первом издании и M48 во втором.
  6. ^ Тарьян, Роберт (1972), «Сортировка с использованием сетей очередей и стеков», Журнал ACM , 19 (2): 341–346, doi : 10.1145/321694.321704 , MR  0298803, S2CID  13608929.
  7. ^ ab Pratt, Vaughan R. (1973), "Вычислительные перестановки с двухсторонними очередями. Параллельные стеки и параллельные очереди", Proc. Fifth Annual ACM Symposium on Theory of Computing (Остин, Техас, 1973) , стр. 268–277, doi : 10.1145/800125.804058 , MR  0489115, S2CID  15740957.
  8. ^ Розенштиль, Пьер ; Тарьян, Роберт (1984), «Коды Гаусса, планарные гамильтоновы графы и сортируемые стеком перестановки», Журнал алгоритмов , 5 (3): 375–390, doi :10.1016/0196-6774(84)90018-X, MR  0756164.
  9. ^ Симион, Родика ; Шмидт, Франк В. (1985), «Ограниченные перестановки», Европейский журнал комбинаторики , 6 (4): 383–406, doi : 10.1016/s0195-6698(85)80052-4 , MR  0829358.
  10. ^ Классон, Андерс; Китаев, Сергей (2008), «Классификация биекций между 321 и 132, избегающими перестановок», Séminaire Lotharingien de Combinatoire , 60 : B60d, 30pp, arXiv : 0805.1325 , MR  2465405.
  11. ^ Станкова, Звезделина (1994), «Запрещенные подпоследовательности», Дискретная математика , 132 (1–3): 291–316, doi : 10.1016/0012-365X(94)90242-9 , MR  1297387.
  12. ^ Станкова, Звезделина; Уэст, Джулиан (2002), «Новый класс эквивалентных по Вильфу перестановок», Журнал алгебраической комбинаторики , 15 (3): 271–290, arXiv : math/0103152 , doi :10.1023/A:1015016625432, MR  1900628, S2CID  13921676.
  13. ^ Бакелин, Йорген; Уэст, Джулиан; Синь, Гуоче (2007), «Эквивалентность Вильфа для классов синглтонов», Advances in Applied Mathematics , 38 (2): 133–149, doi : 10.1016/j.aam.2004.11.006 , MR  2290807.
  14. ^ Бона, Миклош (1997), «Точное перечисление перестановок, избегающих 1342: тесная связь с помеченными деревьями и планарными картами», Журнал комбинаторной теории , Серия A, 80 (2): 257–272, arXiv : math/9702223 , doi : 10.1006/jcta.1997.2800, MR  1485138, S2CID  18352890.
  15. ^ Гессель, Айра М. (1990), «Симметричные функции и P -рекурсивность», Журнал комбинаторной теории , Серия A, 53 (2): 257–285, doi : 10.1016/0097-3165(90)90060-A , MR  1041448.
  16. ^ Маркус, Адам; Тардос, Габор (2004), «Исключенные матрицы перестановок и гипотеза Стэнли-Вильфа», Журнал комбинаторной теории , Серия A, 107 (1): 153–160, doi : 10.1016/j.jcta.2004.04.002 , MR  2063960.
  17. ^ Вильф, Герберт (2002), «Модели перестановок», Дискретная математика , 257 (2): 575–583, doi : 10.1016/S0012-365X(02)00515-0 , MR  1935750.
  18. ^ Саган, Брюс ; Ваттер, Винс (2006), «Функция Мёбиуса композиционного частично упорядоченного множества», Журнал алгебраической комбинаторики , 24 (2): 117–136, arXiv : math/0507485 , doi :10.1007/s10801-006-0017-4, MR  2259013, S2CID  11283347.
  19. ^ Бурштейн, Александр; Елинек, Вит; Елинкова, Ева; Штайнгримссон, Эйнар (2011), «Функция Мёбиуса разделимых и разложимых перестановок», Журнал комбинаторной теории , Серия A, 118 (1): 2346–2364, doi : 10.1016/j.jcta.2011.06.002 , MR  2834180, S2CID  13978488.
  20. ^ Бригналл, Роберт; Елинек, Вит; Кинчл, Ян; Марчант, Дэвид (2019), «Нули функции Мёбиуса перестановок» (PDF) , Mathematika , 65 (4): 1074–1092, arXiv : 1810.05449 , doi : 10.1112/S0025579319000251, MR  3992365, S2CID  53366318
  21. ^ Марчант, Дэвид (2020), «Перестановки 2413-шариков и рост функции Мёбиуса», Электронный журнал комбинаторики , 27 (1): Статья P1.7, 18 стр., arXiv : 1812.05064 , doi : 10.37236/8554
  22. ^ ab Bose, Prosenjit ; Buss, Jonathan F.; Lubiw, Anna (март 1998), "Соответствие шаблону для перестановок", Information Processing Letters , 65 (5): 277–283, doi :10.1016/S0020-0190(97)00209-3
  23. ^ Гиймо, Сильвен; Маркс, Даниэль (2014). «Поиск малых закономерностей в перестановках за линейное время». Труды Двадцать пятого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 20. arXiv : 1307.3073 . doi : 10.1137/1.9781611973402.7. ISBN 978-1-61197-338-9. S2CID  1846959.
  24. ^ Брунер, Мари-Луиза; Лакнер, Мартин (2013), «Вычислительный ландшафт шаблонов перестановок», Чистая математика и приложения , 24 (2): 83–101, arXiv : 1301.0340
  25. ^ Кубица, М.; Кульчинский, Т.; Радошевский, Дж.; Риттер, В.; Валень, Т. (2013), «Линейный алгоритм времени для последовательного сопоставления шаблонов перестановок», Information Processing Letters , 113 (12): 430–433, doi :10.1016/j.ipl.2013.03.015
  26. ^ ab Jelínek, Vít; Kynčl, Jan (2017). «Тяжесть сопоставления шаблонов перестановок». Труды двадцать восьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2017, Барселона, Испания, отель Porta Fira, 16-19 января . SIAM. стр. 378–396. arXiv : 1608.00529 . doi : 10.1137/1.9781611974782.24.
  27. ^ Гиймо, Сильвен; Виалетт, Стефан (2009), «Соответствие шаблону для перестановок, избегающих 321», Алгоритмы и вычисления , Конспект лекций по информатике, т. 5878, стр. 1064–1073, arXiv : 1511.01770 , doi : 10.1007/978-3-642-10631-6_107, ISBN 978-3-642-10630-9
  28. ^ Альберт, Майкл ; Лакнер, Мари-Луиз; Лакнер, Мартин; Ваттер, Винсент (2016), «Сложность сопоставления шаблонов для перестановок, избегающих 321 и перекошенных», Дискретная математика и теоретическая информатика , 18 (2), arXiv : 1510.06051 , doi : 10.46298/dmtcs.1308, S2CID  5827603
  29. ^ Елинек, Вит; Оплер, Михал; Пекарек, Якуб (2021). «Сетки перестановок и сложность сопоставления с образцом». 46-й Международный симпозиум по математическим основам информатики, MFCS 2021, 23-27 августа 2021, Таллинн, Эстония . Замок Дагштуль - Центр информатики Лейбница. стр. 65:1–65:22. arXiv : 2107.10897 . doi : 10.4230/LIPIcs.MFCS.2021.65 .
  30. ^ abc Price, Alkes (1997), Плотности упаковки слоистых узоров, докторская диссертация, Университет Пенсильвании, ProQuest  304421853.
  31. ^ Альберт, Майкл Х.; Аткинсон, МД; Хэндли, CC; Холтон, ДА; Стромквист, В. (2002), "О плотностях упаковки перестановок", Электронный журнал комбинаторики , 9 : Статья R5, 20 стр., doi : 10.37236/1622 , MR  1887086.
  32. ^ Presutti, Cathleen Battiste; Stromquist, Walter (2010), «Скорости упаковки мер и гипотеза о плотности упаковки 2413», в Linton, Steve; Ruškuc, Nik; Vatter, Vincent (ред.), Permutation Patterns , London Math. Soc. Lecture Notes, т. 376, Cambridge University Press, стр. 287–316, doi :10.1017/CBO9780511902499.015, ISBN 978-0-521-72834-8.
  33. ^ Арратия, Ричард (1999), «О гипотезе Стэнли-Вильфа для числа перестановок, избегающих заданного шаблона», Electronic Journal of Combinatorics , 6 : Статья N1, 4 стр., doi : 10.37236/1477 , MR  1710623.
  34. ^ Энджен, Майкл; Ваттер, Винсент (2021), «Содержащие все перестановки», American Mathematical Monthly , 128 (1): 4–24, arXiv : 1810.08252 , doi : 10.1080/00029890.2021.1835384
  35. ^ Эрикссон, Хенрик; Эрикссон, Киммо; Линуссон, Сванте; Вестлунд, Йохан (2007), «Плотная упаковка шаблонов в перестановке», Annals of Combinatorics , 11 (3–4): 459–470, doi : 10.1007/s00026-007-0329-7, MR  2376116, S2CID  2021533.
  36. ^ Бабсон, Эрик; Штайнгримссон, Эйнар (2000), «Обобщенные шаблоны перестановок и классификация статистик Махона», Séminaire Lotharingien de Combinatoire , 44 : Исследовательская статья B44b, 18 стр., MR  1758852.
  37. ^ Уэст, Джулиан (1993), «Сортировка дважды через стек», Теоретическая информатика , 117 (1–2): 303–313, doi : 10.1016/0304-3975(93)90321-J , MR  1235186.
  38. ^ Буске-Мелу, Мирей ; Батлер, Стив (2007), «Лесоподобные перестановки», Annals of Combinatorics , 11 (3–4): 335–354, arXiv : math/0603617 , doi :10.1007/s00026-007-0322-1, MR  2376109, S2CID  31236417.

Внешние ссылки

На Викискладе есть медиафайлы по теме «Шаблоны перестановок» .

Конференция по моделям перестановок проводится ежегодно с 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 г., Университет Флоренции , Флоренция, Италия.
  8. Permutation Patterns 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. Permutation Patterns 2015, 15–19 июня 2015 г., De Morgan House, Лондон, Англия.
  14. Шаблоны перестановок 2016, 27 июня – 1 июля 2016 г., Университет Говарда , Вашингтон, округ Колумбия, США.
  15. Permutation Patterns 2017, 26–30 июня 2017 г., Университет Рейкьявика , Рейкьявик, Исландия.
  16. Шаблоны перестановок 2018, 9–13 июля 2018 г., Дартмутский колледж , Хановер, Нью-Гемпшир, США.
  17. Permutation Patterns 2019, 17–21 июня 2019 г., Universität Zürich , Цюрих, Швейцария.
  18. Виртуальный семинар «Permutation Patterns 2020», 30 июня – 1 июля 2020 г., организованный Университетом Вальпараисо , Вальпараисо, Индиана, США.
  19. Виртуальный семинар «Permutation Patterns 2021», 15–16 июня 2021 г., организованный Университетом Стратклайда , Глазго, Шотландия.
  20. Шаблоны перестановок 2022, 20–24 июня 2022 г., Университет Вальпараисо , Вальпараисо, Индиана, США.
  21. Шаблоны перестановок 2023, 3–7 июля 2023 г., Университет Бургундии , Дижон, Франция.

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

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

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