Суперпаттерн - Superpattern

В математическом исследовании перестановки и шаблоны перестановок, а суперпаттерн или же универсальная перестановка - это перестановка, содержащая все шаблоны заданной длины. В частности, k-суперпаттерн содержит все возможные шаблоны длины k.[1]

Определения и пример

Если π - перестановка длины п, представленный как последовательность чисел от 1 до п в некотором порядке, и s = s1, s2, ..., sk является подпоследовательностью π длины k, тогда s соответствует уникальному шаблон, перестановка длины k элементы которого расположены в том же порядке, что и s. То есть для каждой пары я и j индексов, яй элемент шаблона для s должно быть меньше, чем jэлемент тогда и только тогда, когда яй элемент s меньше, чем jй элемент. Эквивалентно шаблон порядково-изоморфный к подпоследовательности. Например, если π - это перестановка 25314, то она имеет десять подпоследовательностей длины три, образующих следующие шаблоны:

ПодпоследовательностьШаблон
253132
251231
254132
231231
234123
214213
531321
534312
514312
314213

Подстановка π называется k-суперпаттерн, если его образцы длины k включать всю длинуk перестановки. Например, паттерны длины 3 для 25314 включают в себя все шесть перестановок длины 3, так что 25314 - это суперподобный 3-паттерн. Никакой 3-супершаттерн не может быть короче, потому что любые две подпоследовательности, которые образуют два шаблона 123 и 321, могут пересекаться только в одной позиции, поэтому пять символов требуются только для покрытия этих двух шаблонов.

Границы длины

Arratia  (1999 ) ввел задачу определения длины кратчайшего из возможных k-суперпаттерн.[2] Он заметил, что существует суперпаттерн длины k2 (предоставлено лексикографический порядок на векторах координат точек в квадратной сетке), а также заметил, что для суперподхода длины п, он должен иметь как минимум столько же подпоследовательностей, сколько существует шаблонов. То есть должно быть правда, что , откуда следует Приближение Стирлинга который п ≥ k2/е2, куда е ≈ 2,71828 составляет Число Эйлера Позднее эта нижняя граница была немного улучшена Хроманом, Кваном и Сингалом (2020 ), который увеличил его до 1.000076k2/е2,[3] опровергающий Arratia предположение, что k2/е2 нижняя граница была жесткой.[2]

Верхняя граница k2 на длине суперпаттерна, доказанной Арратией, не является тесным. После промежуточных доработок[4],Миллер  (2009 ) доказал, что существует k-суперпаттерн длиной не более k(k + 1) / 2 за каждые k.[5]Эта оценка была позже улучшена Энгеном и Ваттером (2019 ), который снизил его до ⌈ (k2 + 1)/2⌉.[6]

Эрикссон и др. предположил, что истинная длина кратчайшего k-суперпаттерн асимптотичен k2/2.[4]Однако это противоречит гипотезе Алон по случайным суперпаттернам описанным ниже.

Случайные суперпаттерны

Исследователи также изучили длину, необходимую для того, чтобы последовательность, сгенерированная случайным процессом, превратилась в суперпроцесс.[7] Арратия (1999) замечает это, потому что самая длинная возрастающая подпоследовательность случайной перестановки имеет длину (с большой вероятностью) примерно 2√п, то случайная перестановка должна иметь длину не менее k2/ 4 иметь высокую вероятность быть k-superpattern: перестановки короче, чем это, скорее всего, не будут содержать шаблон идентичности.[2] Он приписывает Алон гипотеза о том, что для любого ε> 0 с большой вероятностью случайные перестановки длины k2/ (4 −ε) будет k-суперпаттерны.

Смотрите также

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

  1. ^ Бона, Миклош (2012), Комбинаторика перестановок, Дискретная математика и ее приложения, 72 (2-е изд.), CRC Press, стр. 227, ISBN  9781439850510.
  2. ^ а б c Арратия, Ричард (1999), «О гипотезе Стэнли-Уилфа о количестве перестановок, избегающих данного шаблона», Электронный журнал комбинаторики, 6: N1, Дои:10.37236/1477, МИСТЕР  1710623
  3. ^ Хроман, Захари; Кван, Мэтью; Сингхал, Михир (2020), Нижние оценки суперпаттернов и универсальных последовательностей, arXiv:2004.02375
  4. ^ а б Эрикссон, Хенрик; Эрикссон, Киммо; Линюссон, Сванте; Wästlund, Johan (2007), "Плотная упаковка паттернов в перестановке", Анналы комбинаторики, 11 (3–4): 459–470, Дои:10.1007 / s00026-007-0329-7, МИСТЕР  2376116
  5. ^ Миллер, Элисон (2009), «Асимптотические оценки для перестановок, содержащих множество различных шаблонов», Журнал комбинаторной теории, Серия А, 116 (1): 92–108, Дои:10.1016 / j.jcta.2008.04.007
  6. ^ Энген, Майкл; Ваттер, Винсент (2019), Содержит все перестановки, arXiv:1810.08252, Bibcode:2018arXiv181008252E
  7. ^ Годболе, Анант; Лиендо, Марта (2013), Распределение времени ожидания появления суперпаттернов, arXiv:1302.4668, Bibcode:2013arXiv1302.4668G.