スタンレー・ウィルフ予想

1980年代後半にリチャード・P・スタンレーとハーバート・ウィルフがそれぞれ独立に定式化したスタンレー・ウィルフ予想は、すべての適切な順列クラスの成長率が単指数関数的であることを述べている。これはアダム・マーカスとガボール・タルドス（2004 ）によって証明され、もはや予想ではない。マーカスとタルドスは実際にはゾルタン・フュレディとペーター・ハジナル（1992 ）による別の予想を証明したが、この予想はクラザール（2000）によってスタンレー・ウィルフ予想を導くことが示されていた。  

スタンレー・ウィルフ予想は、任意の順列βに対して、β を順列パターンとして避ける長さnの順列の数 | S _n ( β )| が最大でC ⁿとなるような定数Cが存在すると述べている。アラティア (1999) が指摘したように、これは極限の収束と同等である。

${\displaystyle \lim _{n\to \infty }{\sqrt[{n}]{|S_{n}(\beta )|}}.}$

マーカスとタルドスが与えたCの上限はβの長さに対して指数関数的である。アラティア (1999)のより強い予想では、 C を( k − 1) ²とすることができるとされていたが、ここでk はβの長さを表す。しかし、この予想は、置換β = 4231に対してAlbert ら (2006)によって反証された。実際、Fox (2013) は、 Cが実際にはほとんどすべての置換に対してkに対して指数関数的であることを示した。

順列クラスの成長率（またはスタンレー・ウィルフ限界）は次のように定義される。

${\displaystyle \limsup _{n\to \infty }{\sqrt[{n}]{a_{n}}},}$

ここで、n_はクラス内の長さnの順列の数を表します。明らかに、単一の禁止パターンで定義されるか、禁止パターンの集合で定義されるかにかかわらず、すべての正の実数が順列クラスの成長率になるわけではありません。たとえば、厳密に 0 から 1 の間の数は、順列クラスの成長率にはなり得ません。

カイザーとクラザー（2002）は、長さnのクラスの順列の数がn番目のフィボナッチ数より小さい場合、そのクラスの列挙は最終的に多項式になることを証明しました。したがって、厳密に 1 と黄金比の間の数も順列クラスの成長率にはなり得ません。カイザーとクラザーはさらに、2 未満の順列クラスのすべての可能な成長定数を確立しました。これらは多項式の最大の実根です。

${\displaystyle x^{k+1}-2x^{k}+1}$

整数k  ≥  2 の場合。これは、2 が順列クラスの成長率の最小蓄積点であることを示しています。

Vatter (2011)は後に、置換クラスの成長率の特性を特定の代数的数 κ≈2.20 まで拡張しました。この特性から、κ は成長率の集積点の最小集積点であり、κ までのすべての成長率は代数的数であることが導かれます。Vatter (2019)は、ξ ≈ 2.31 という代数的数が存在し、ξ の任意の近傍には非可算個の成長率が存在するが、それより小さい成長率は可算個しかないことを明らかにしました。Pantone & Vatter (2020)は、ξ より小さい (可算個) 成長率を特性化し、それらはすべて代数的数でもあります。彼らの結果はまた、置換クラスのすべての成長率の集合において、ξ が上からの最小集積点であることを示唆しています。

反対の方向では、Vatter (2010) は、2.49 以上のすべての実数が順列クラスの成長率であることを証明した。この結果は後にBevan (2018)によって改良され、2.36 以上のすべての実数が順列クラスの成長率であることを証明した。

• 特定の順列クラスの成長率に関する、特定の順列クラスの列挙。

• Albert, Michael H. ; Elder, Murray; Rechnitzer, Andrew; Westcott, P.; Zabrocki, Mike (2006)、「4231回避順列のStanley–Wilf極限とArratiaの予想について」、Advances in Applied Mathematics、36 (2): 96–105、arXiv : math/0502504、doi : 10.1016/j.aam.2005.05.007、hdl : 10453/98769、MR 2199982 。
• Arratia, Richard (1999)、「与えられたパターンを避ける順列の数に関するスタンレー・ウィルフ予想について」、Electronic Journal of Combinatorics、6 :N1、doi : 10.37236/1477、MR 1710623 。
• Bevan, David (2018) [2014]、「順列クラスの成長率の区間」、Combinatorica、38 (2): 279–303、arXiv : 1410.3679、Bibcode : 2014arXiv1410.3679B、doi : 10.1007/s00493-016-3349-2、S2CID 254031975 。
• Fox, Jacob (2013), Stanley–Wilf の限界は典型的には指数関数的である、arXiv : 1310.8378、Bibcode : 2013arXiv1310.8378F。
• Furedi, ゾルタン; Hajnal、Péter (1992)、「Davenport–Schinzel Theory of matrices」、離散数学、103 (3): 233–251、doi : 10.1016/0012-365X(92)90316-8、MR 1171777 。
• Kaiser, Tomáš; Klazar, Martin (2002年3月)、「閉じた順列クラスの成長率について」、電子組合せ論ジャーナル、9 (2):研究論文10、20、MR 2028280 。
• Klazar, Martin (2000)、「Füredi–Hajnal予想はStanley–Wilf予想を含意する」、形式的冪級数と代数的組合せ論（モスクワ、2000年）、Springer、pp. 250–255、MR 1798218  。
• Klazar, Martin (2010)、「組合せ列挙におけるいくつかの一般的な結果」、順列パターン、ロンドン数学会講義ノートシリーズ、第 376巻、ケンブリッジ：ケンブリッジ大学出版局、3–40ページ、 doi ： 10.1017 /CBO9780511902499.002、ISBN  978-0-521-72834-8MR 2732822​ 。
• Marcus, Adam ; Tardos, Gábor (2004)、「除外された順列行列とスタンレー・ウィルフ予想」、Journal of Combinatorial Theory、シリーズA、107 (1): 153–160、doi : 10.1016/j.jcta.2004.04.002、MR 2063960 。
• Pantone, Jay; Vatter, Vincent (2020)、「順列クラスの成長率：非可算性の閾値までの分類」、Israel Journal of Mathematics、236 (1): 1–43、arXiv : 1605.04289、doi : 10.1007/s11856-020-1964-5、MR 4093880 。
• Vatter, Vincent (2019)、「順列クラスの成長率：可算から非可算へ」、Proc. London Math. Soc.、シリーズ3、119 ( 4): 960–997、arXiv : 1605.04297、doi : 10.1112/plms.12250、MR 3964825、S2CID 118595642  。
• Vatter, Vincent (2010)、「2.48188を超えるすべての成長率の順列クラス」、Mathematika、56 (1): 182–192、arXiv : 0807.2815、doi : 10.1112/S0025579309000503、MR 2604993、S2CID 228723  。
• Vatter, Vincent (2011)、「小さな順列クラス」、Proc. London Math. Soc.、シリーズ3、103 ( 5): 879–921、arXiv : 0712.4006、doi : 10.1112/plms/pdr017、MR 2852292、S2CID 16116435  。

• アダム・マーカスとガボール・タルドスがスタンレー・ウィルフ予想をいかにして分割して解決したか―ドロン・ツァイルベルガー著
• ワイススタイン、エリック・W. 「スタンレー・ウィルフ予想」 . MathWorld .