Loading article…
順列と順列パターンの数学的研究において、スーパーパターンまたは普遍順列とは、与えられた長さのすべてのパターンを含む順列のことである。より具体的には、k-スーパーパターンは長さkのすべての可能なパターンを含む。[ 1 ]
π が長さnの順列であり、1 からnまでの数字を何らかの順序で並べた数列として表され、s = s 1 , s 2 , ..., s kが π の長さkの部分列である場合、s は一意のパターン、つまり要素がsと同じ順序である長さkの順列に対応します。つまり、インデックスのペアiとjのそれぞれについて、 sのパターンのi番目の要素がj番目の要素より小さいのは、 sのi番目の要素がj番目の要素より小さい場合に限ります。言い換えれば、パターンは部分列と順序同型です。たとえば、π が順列 25314 である場合、長さ 3 の部分列が 10 個あり、次のパターンを形成します。
順列 πの長さkのパターンが、長さkの順列すべてを含む場合、π はkスーパーパターンと呼ばれます。たとえば、25314 の長さ 3 のパターンは、長さ 3 の順列 6 つすべてを含むため、25314 は 3 スーパーパターンです。3 スーパーパターンはこれより短くすることはできません。なぜなら、2 つのパターン 123 と 321 を形成する任意の 2 つの部分列は、1 つの位置でしか交差しないため、これら 2 つのパターンをカバーするには 5 つのシンボルが必要になるからです。
Arratia ( 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 ] 。
Arratia によって証明されたスーパーパターンの長さの上限k 2は厳密ではありません。中間的な改善の後、[ 4 ] Miller ( 2009 )は、すべてのkに対して長さが最大でk ( k + 1)/2のkスーパーパターンが存在することを証明しました。[ 5 ]この上限は後にEngenとVatter ( 2021 ) によって改善され 、⌈( k 2 + 1)/2⌉ に引き下げられました。[ 6 ]
エリクソンらは、最短のkスーパーパターンの真の長さはk 2 /2に漸近すると推測した。 [ 4 ]しかし、これは、後述するランダムスーパーパターンに関するアロン の推測と矛盾する。
研究者たちは、ランダムなプロセスによって生成されたシーケンスがスーパーパターンになるために必要な長さについても研究してきた。[ 7 ] Arratia (1999)は、ランダムな順列の最長増加部分列の長さが (高い確率で) 約2√nであることから、ランダムな順列がkスーパーパターンになる確率が高いためには、少なくともk 2 /4 の長さが必要であると指摘している。これより短い順列は、おそらく同一パターンを含まないだろう。[ 2 ]彼は、任意のε > 0に対して、高い確率で、長さk 2 /(4 − ε)のランダムな順列がkスーパーパターンになるという予想を Alon に帰している。
