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

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

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

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

Подпоследовательность	Шаблон
253	132
251	231
254	132
231	231
234	123
214	213
531	321
534	312
514	312
314	213

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

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

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

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

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

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

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

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

• Суперперестановка

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