В математическом исследовании перестановок и шаблонов перестановок супершаблон или универсальная перестановка — это перестановка, которая содержит все шаблоны заданной длины. Более конкретно, 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, то она имеет десять подпоследовательностей длины три, образуя следующие шаблоны:
Перестановка π называется k -супершаблоном, если ее шаблоны длины k включают все перестановки длины k . Например, шаблоны длины 3 25314 включают все шесть перестановок длины 3, поэтому 25314 является 3-супершаблоном. Никакой 3-супершаблон не может быть короче, потому что любые две подпоследовательности, которые образуют два шаблона 123 и 321, могут пересекаться только в одной позиции, поэтому для покрытия этих двух шаблонов требуется пять символов.
Арратия (1999) ввел задачу определения длины кратчайшего возможного k -супершаблона. [2] Он заметил, что существует супершаблон длины k 2 (заданный лексикографическим упорядочением координатных векторов точек в квадратной сетке), а также заметил, что для супершаблона длины n должно быть так, что он имеет по крайней мере столько же подпоследовательностей, сколько имеется шаблонов. То есть должно быть верно, что , из чего следует по приближению Стирлинга , что n ≥ k 2 / e 2 , где e ≈ 2,71828 — число Эйлера . Эта нижняя граница была позже немного улучшена Хроманом, Кваном и Сингхалом (2021), которые увеличили ее до 1,000076 k 2 / e 2 , [3] опровергнув гипотезу Арратии о том, что нижняя граница k 2 / e 2 была точной. [2]
Верхняя граница длины суперпаттерна k 2 , доказанная Арратией, не является жесткой. После промежуточных улучшений [4] Миллер (2009) доказал, что существует k -суперпаттерн длины не более k ( k + 1)/2 для каждого k . [5] Эта граница была позже улучшена Энгеном и Ваттером (2021), которые снизили ее до ⌈( k 2 + 1)/2⌉. [6]
Эрикссон и др . предположили, что истинная длина кратчайшего k -супершаблона асимптотически равна k2 /2. [4] Однако это противоречит гипотезе Алона о случайных супершаблонах, описанной ниже.
Исследователи также изучали длину, необходимую для того, чтобы последовательность, сгенерированная случайным процессом, стала супершаблоном. [7] Арратия (1999) замечает, что, поскольку самая длинная возрастающая подпоследовательность случайной перестановки имеет длину (с высокой вероятностью) приблизительно 2√ n , из этого следует, что случайная перестановка должна иметь длину по крайней мере k 2 /4, чтобы иметь высокую вероятность быть k -супершаблоном: перестановки короче этой, скорее всего, не будут содержать тождественный шаблон. [2] Он приписывает Алону гипотезу о том, что для любого ε > 0 с высокой вероятностью случайные перестановки длины k 2 /(4 − ε) будут k -супершаблонами.
