В математическом исследовании перестановок и шаблонов перестановок , superpattern или универсальная перестановка перестановка , которая содержит все шаблоны заданной длины. В частности, 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 |
Перестановка π называется к -superpattern , если его структура длиной к включает все длина- K перестановок. Например, паттерны длины 3 для 25314 включают в себя все шесть перестановок длины 3, так что 25314 - это суперподборка из трех. Никакой 3-супершаттерн не может быть короче, потому что любые две подпоследовательности, которые образуют два шаблона 123 и 321, могут пересекаться только в одной позиции, поэтому пять символов требуются только для покрытия этих двух шаблонов.
Ограничения длины [ править ]
Арратиа ( 1999 ) ввел проблему определения длины кратчайшего из возможных k -суперпаттернов. [2] Он заметил, что существует суперподбор длины k 2 (заданный лексикографическим порядком координатных векторов точек в квадратной сетке), а также заметил, что для супершаблона длины n это должно быть так, что он имеет как минимум столько же подпоследовательностей, сколько существует шаблонов. То есть должно быть верно то , что из приближения Стирлинга следует , что n ≥ k 2 / e 2 , где e ≈ 2,71828 - число Эйлера . Позднее эта нижняя граница была улучшена очень незначительно хроман, Kwan и Singhal ( 2020 ), который увеличился его 1.000076 к 2 / е 2 , [3] опровергая Арратья гипотеза «ы , что к 2 / е 2 нижняя граница была жесткой. [2]
Верхняя граница k 2 для длины суперсвета, доказанная Арратиа, не является точной. После промежуточных улучшений [4] Миллер ( 2009 ) доказал, что существует k -суперпаттерн длины не более k ( k + 1) / 2 для любого k . [5] Эта оценка была позже улучшена Энгеном и Ваттером ( 2019 ), которые понизили ее до ⌈ ( k 2 + 1) / 2⌉. [6]
Эрикссон и др. высказал предположение , что истинная длина самой короткой к -superpattern является асимптотической к 2 /2. [4] Однако это противоречит гипотезе Алона о случайных суперкартах, описанной ниже.
Случайные суперпаттерны [ править ]
Исследователи также изучили длину, необходимую для того, чтобы последовательность, сгенерированная случайным процессом, превратилась в суперсистему. [7] Аррат (1999) отмечают , что, так как длинная увеличение подпоследовательность случайной перестановки имеет длину (с высокой вероятностью) приблизительно 2√ п , то отсюда следует , что случайная перестановка должна иметь длину , по меньшей мере , к 2 /4 имеет высокую вероятность быть k -суперпаттерном: перестановки короче, чем это, скорее всего, не будут содержать шаблон идентичности. [2] Он приписывает Алону гипотезу о том, что для любого ε> 0 с большой вероятностью случайные перестановки длины k 2/ (4 - ε) будут k -суперпаттернами.
См. Также [ править ]
Ссылки [ править ]
- ^ Бона, Миклош (2012), Комбинаторика перестановок , Дискретная математика и ее приложения, 72 (2-е изд.), CRC Press, стр. 227, ISBN 9781439850510.
- ^ a b c Арратия, Ричард (1999), «О гипотезе Стэнли-Уилфа для числа перестановок, избегающих данного шаблона» , Электронный журнал комбинаторики , 6 : N1, doi : 10.37236 / 1477 , MR 1710623
- ^ Хроман, Захари; Кван, Мэтью; Сингхал, Михир (2020), Нижние границы для суперпаттернов и универсальных последовательностей , arXiv : 2004.02375
- ^ а б Эрикссон, Хенрик; Эрикссон, Киммо; Линюссон, Сванте; Wästlund, Йохан (2007), "плотная упаковка узоры в перестановке", Анналы Комбинаторика , 11 (3-4): 459-470, DOI : 10.1007 / s00026-007-0329-7 , МР 2376116
- ^ Миллер, Элисон (2009), «Асимптотические границы для перестановок, содержащих множество различных шаблонов», Журнал комбинаторной теории , серия A, 116 (1): 92–108, DOI : 10.1016 / j.jcta.2008.04.007
- ^ Энген, Майкл; Vatter, Винсент (2021), "Содержит все перестановки", American Mathematical Monthly , 128 (1): 4-24, DOI : 10,1080 / 00029890.2021.1835384
- ^ Годболе, Анант; Лиендо, Марта (2013), Распределение времени ожидания для появления суперпаттернов , arXiv : 1302.4668 , Bibcode : 2013arXiv1302.4668G.
