スーパーパターン

順列および順列パターンの数学的研究において、スーパーパターンまたは普遍順列とは、与えられた長さのパターンをすべて含む順列のことである。より具体的には、kスーパーパターンは長さkのすべての可能なパターンを含む。^{[ 1 ]}

定義と例

π が長さnの順列で、 1 からnまでの数字をある順序で並べたシーケンスとして表現され、s  =  s ₁、s ₂、...、s _{k が}長さkの π の部分シーケンスである場合、s は、要素がsと同じ順序である長さkの順列である一意のパターンに対応します。つまり、インデックスの各ペアiとjについて、 sのパターンのi番目の要素がj番目の要素より小さい場合のみ、sのi番目の要素はj番目の要素より小さくなります。同様に、パターンは部分シーケンスと順序同型です。たとえば、 π が順列 25314 である場合、長さ 3 の部分シーケンスが 10 個あり、次のパターンを形成します。

部分列	パターン
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の順列の6つすべてを含むため、25314は3-スーパーパターンです。パターン123と321を形成する任意の2つの部分列は、1つの位置でしか交差しないため、3-スーパーパターンはこれより短くなることはなく、この2つのパターンをカバーするだけでも5つの記号が必要です。

長さの境界

Arratia  ( 1999 ) は、可能な限り短いkスーパーパターンの長さを決定する問題を紹介しました。^{[ 2 ]}彼は、長さk ²のスーパーパターン(正方格子内の点の座標ベクトルの辞書式順序で与えられる) が存在することを観察し、長さnのスーパーパターンでは、パターンの数と同じ数以上のサブシーケンスがなければならないことも観察しました。つまり、が真でなければならないので、スターリングの近似によりn  ≥  k ² / e ²が成り立ちます。ここで、e  ≈ 2.71828 はオイラー数です。この下限値は後にクロマン、クワン、シンガル（ 2021 ）によってわずかに改善され、1.000076 k ² / e ²に増加しました。^{[ 3 ]} k ² / e ^{2の下限値は厳密であるという}アラティアの予想を反証しました。^{[ 2 ]}${\displaystyle {\tbinom {n}{k}}\geq k!}$

Arratiaによって証明されたスーパーパターンの長さのk ²の上限は厳密ではない。中間的な改良を経て、^{[ 4 ]} Miller  ( 2009 )は、任意のkに対して長さが最大でk ( k  + 1)/2のkスーパーパターンが存在することを証明した。^{[ 5 ]} この上限は後にEngenとVatter ( 2021 )によって改良され、⌈( k ² + 1)/2⌉まで引き下げられた 。^{[ 6 ]}

エリクソンらは、最短のk超パターンの真の長さはk2 / ²に漸近すると予想した。^{[ 4 ]}しかし、これは後述するランダム超パターンに関する アロン の予想と矛盾している。

ランダムスーパーパターン

研究者たちは、ランダムプロセスによって生成されたシーケンスがスーパーパターンになるために必要な長さも研究してきました。^{[ 7 ]} Arratia (1999)は、ランダム順列の最長増加サブシーケンスの長さは (高い確率で) 約2√nであるため、ランダム順列がkスーパーパターンになる確率が高くなるためには、ランダム順列の長さは少なくともk ² /4 でなければならないと指摘しています。これより短い順列には、アイデンティティパターンが含まれない可能性があります。^{[ 2 ]}彼は、任意のε > 0に対して、高い確率で長さk ² /(4 − ε)のランダム順列がkスーパーパターンになるという予想をAlonに帰しています。

参照

• 超順列

参考文献

1. Bóna, Miklós (2012),順列の組合せ論、離散数学とその応用、第72巻（第2版）、CRC Press、p. 227、ISBN 9781439850510。
2. Arratia, Richard (1999)、「与えられたパターンを回避する順列の数に関するスタンレー・ウィルフ予想について」、Electronic Journal of Combinatorics、6 : N1、doi : 10.37236/1477、MR 1710623 
3. Chroman, Zachary; Kwan, Matthew; Singhal, Mihir (2021)、「スーパーパターンとユニバーサルシーケンスの下限値」、Journal of Combinatorial Theory、シリーズA、182、論文番号105467（15 pp）、arXiv：2004.02375、doi：10.1016/j.jcta.2021.105467、MR 4253319 
4. エリクソン、ヘンリック;エリクソン、キンモ。スヴァンテ・リナソン。 Wästlund、Johan (2007)、「順列におけるパターンの高密度パッキング」、Annals of Combinatorics、11 ( 3–4 ): 459–470、doi : 10.1007/s00026-007-0329-7、MR 2376116、S2CID 2021533  
5. ミラー、アリソン（2009）、「多くの異なるパターンを含む順列の漸近的境界」、Journal of Combinatorial Theory、シリーズA、116（1）：92–108、doi：10.1016/j.jcta.2008.04.007
6. エンゲン、マイケル；ヴァッター、ヴィンセント（2021）「すべての順列を含む」アメリカ数学月刊誌、128（1）：4–24、arXiv：1810.08252、doi：10.1080/00029890.2021.1835384
7. Godbole, Anant P.; Liendo, Martha (2016)、「スーパーパターンの出現に対する待ち時間分布」、応用確率論における方法論と計算、18 (2): 517– 528、arXiv : 1302.4668、doi : 10.1007/s11009-015-9439-6、MR 3488590