Суперпаттерн
В математическом исследовании перестановок и шаблонов перестановок супершаблон универсальная или перестановка — это перестановка, которая содержит все шаблоны заданной длины. Точнее, k -супершаблон содержит все возможные шаблоны длины k . [1]
Определения и пример
[ редактировать ]Если π — перестановка длины n , представленная как последовательность чисел от 1 до n в некотором порядке, и s = s 1 , s 2 , ..., s k — подпоследовательность π длины k , то s соответствует уникальному шаблону , перестановке длины k , элементы которой находятся в том же порядке, что и s . То есть для каждой пары i и j индексов i -й элемент шаблона для s должен быть меньше j -го элемента тогда и только тогда, когда i -й элемент 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, могут пересекаться только в одной позиции, поэтому только для покрытия этих двух паттернов требуется пять символов.
Ограничения длины
[ редактировать ]Арратиа ( 1999 ) поставил задачу определения длины кратчайшего k -суперпаттерна. [2] Он заметил, что существует суперпаттерн длины k 2 (заданный лексикографическим упорядочением координатных векторов точек в квадратной сетке), а также заметил, что для супершаблона длины n должно быть так, что он имеет по крайней мере столько же подпоследовательностей, сколько существует шаблонов. То есть должно быть верно, что , откуда по аппроксимации Стирлинга следует , что n ≥ k 2 / е 2 , где e ≈ 2,71828 — число Эйлера .Эта нижняя граница позже была немного улучшена за счетХроман, Кван и Сингхал ( 2021 г. ), который увеличил его до 1,000076 тыс. 2 / е 2 , [3] опровергая что гипотезу Арратии о том, k 2 / е 2 нижняя граница была жесткой. [2]
Верхняя граница k 2 на длину супершаблона, доказанную Арратией, не является жесткой. После промежуточных улучшений [4] Миллер ( 2009 ) доказал, что существует k -супершаблон длины не более k ( k + 1)/2 для каждого k . [5] Эта граница позже была улучшенаЭнген и Ваттер ( 2021 ), которые понизили его до ⌈( k 2 + 1)/2⌉. [6]
Эрикссон и др. выдвинул гипотезу, что истинная длина кратчайшего k -суперпаттерна асимптотична k 2 /2. [4] Однако это противоречит гипотезе Алона о случайных суперпаттернах, описанной ниже.
Случайные суперпаттерны
[ редактировать ]Исследователи также изучили длину, необходимую для того, чтобы последовательность, сгенерированная случайным процессом, стала суперпаттерном. [7] Арратиа (1999) отмечает, что, поскольку самая длинная возрастающая подпоследовательность случайной перестановки имеет длину (с высокой вероятностью) примерно 2√ n , отсюда следует, что случайная перестановка должна иметь длину не менее k. 2 /4 имеет высокую вероятность быть k -супершаблоном: более короткие перестановки, скорее всего, не будут содержать тождественный шаблон. [2] Он приписывает Алону гипотезу о том, что для любого ε > 0 с большой вероятностью случайные перестановки длины k 2 /(4 − ε) будут k -суперпаттернами.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Бона, Миклош (2012), Комбинаторика перестановок , дискретная математика и ее приложения, том. 72 (2-е изд.), CRC Press, с. 227, ISBN 9781439850510 .
- ^ Jump up to: Перейти обратно: а б с Арратиа, Ричард (1999), «О гипотезе Стэнли-Уилфа о количестве перестановок, избегающих заданного шаблона» , Electronic Journal of Combinatorics , 6 : N1, doi : 10.37236/1477 , MR 1710623
- ^ Хроман, Закари; Кван, Мэтью; Сингхал, Михир (2021), «Нижние границы суперпаттернов и универсальных последовательностей», Журнал комбинаторной теории , серия A, 182 , статья № 105467 (15 стр.), arXiv : 2004.02375 , doi : 10.1016/j.jcta.2021.105467 , МР 4253319
- ^ Jump up to: Перейти обратно: а б Эрикссон, Хенрик; Эрикссон, Киммо; Линуссон, Сванте; Вестлунд, Йохан (2007), «Плотная упаковка шаблонов в перестановке», Annals of Combinatorics , 11 (3–4): 459–470, doi : 10.1007/s00026-007-0329-7 , MR 2376116 , S2CID 2021533
- ^ Миллер, Элисон (2009), «Асимптотические границы для перестановок, содержащих множество различных шаблонов», Журнал комбинаторной теории , серия A, 116 (1): 92–108, doi : 10.1016/j.jcta.2008.04.007
- ^ Энген, Майкл; Ваттер, Винсент (2021), «Содержит все перестановки», American Mathematical Monthly , 128 (1): 4–24, arXiv : 1810.08252 , doi : 10.1080/00029890.2021.1835384
- ^ Годболе, Анант П.; Лиендо, Марта (2016), «Распределение времени ожидания появления суперпаттернов», Методология и вычисления в прикладной теории вероятностей , 18 (2): 517–528, arXiv : 1302.4668 , doi : 10.1007/s11009-015-9439-6 , МР 3488590