Domněnka Stanleyho a Wilfa - Stanley–Wilf conjecture
The Domněnka Stanleyho a Wilfa, formulované nezávisle Richard P. Stanley a Herbert Wilf na konci 80. let se uvádí, že tempo růstu každého řádného permutační třída je jednotlivě exponenciální. Bylo prokázáno Adam Marcus a Gábor Tardos (2004 ) a již není domněnkou. Marcus a Tardos ve skutečnosti prokázali jinou domněnku Zoltán Füredi a Péter Hajnal (1992 ), o kterém bylo prokázáno, že implikuje Stanley-Wilfův domněnku Klazar (2000).
Prohlášení
Podle domněnky Stanley-Wilf pro každou permutaci β, existuje konstanta C takové, že číslo |Sn(β) | permutací délky n kterým se vyhnout β jako permutační vzor je nanejvýš Cn. Tak jako Arratia (1999) pozorováno, je to ekvivalent konvergence omezit
Horní mez daná Marcusem a Tardosem pro C je exponenciální v délce β. Silnější domněnka Arratia (1999) uvedl, že by se dalo vzít C být (k − 1)2, kde k označuje délku β, ale tato domněnka byla vyvrácena pro permutaci β = 4231 podle Albert a kol. (2006). Vskutku, Fox (2013) to ukázal C je ve skutečnosti exponenciální v k pro téměř všechny obměny.
Přípustné míry růstu
The tempo růstu (nebo Stanley-Wilfův limit) třídy permutace je definována jako
kde An označuje počet permutací délky n ve třídě. Je zřejmé, že ne každé kladné reálné číslo může být rychlostí růstu permutační třídy, bez ohledu na to, zda je definováno jediným zakázaným vzorem nebo sadou zakázaných vzorů. Například čísla striktně mezi 0 a 1 nemohou být mírou růstu permutačních tříd.
Kaiser & Klazar (2002) dokázal, že pokud počet permutací ve třídě délky n je vždy menší než nth Fibonacciho číslo pak je výčet třídy nakonec polynomický. Proto jsou čísla striktně mezi 1 a Zlatý řez také nemohou být rychlosti růstu permutačních tříd. Kaiser a Klazar pokračovali ve stanovování všech možných růstových konstant permutační třídy pod 2; toto jsou největší skutečné kořeny polynomů
pro celé číslo k ≥ 2. To ukazuje, že 2 je nejméně akumulačním bodem rychlostí růstu permutačních tříd.
Vatter (2011) později rozšířil charakterizaci rychlostí růstu permutačních tříd až na κ≈2,20, z čehož vyplývá, že κ je nejméně akumulační bod z akumulačních bodů rychlostí růstu. Míry růstu mezi 2 a κ jsou také algebraické. Vatter (2010) také dokázal, že každé reálné číslo alespoň 2,49 je míra růstu třídy permutace. Bevan (2014) od té doby se zlepšil na tomto výsledku, což ukazuje, že každé reálné číslo alespoň 2,36 je míra růstu třídy permutace.
Viz také
- Výčty konkrétních permutačních tříd pro rychlosti růstu konkrétních permutačních tříd.
Poznámky
Reference
- Albert, Michael H.; Starší, Murray; Rechnitzer, Andrew; Westcott, P .; Zabrocki, Mike (2006), „Na hranici Stanley-Wilf 4231 - vyhýbání se permutacím a domněnka Arratie“, Pokroky v aplikované matematice, 36 (2): 96–105, doi:10.1016 / j.aam.2005.05.007, PAN 2199982.
- Arratia, Richard (1999), „Podle domněnky Stanley-Wilf o počtu permutací, které se vyhýbají danému vzoru, Electronic Journal of Combinatorics, 6: N1, PAN 1710623.
- Bevan, David (2014), Intervaly tempa růstu třídy permutace, arXiv:1410.3679, Bibcode:2014arXiv1410.3679B.
- Fox, Jacob (2013), Limity Stanley-Wilf jsou obvykle exponenciální, arXiv:1310.8378, Bibcode:2013arXiv1310.8378F.
- Füredi, Zoltán; Hajnal, Péter (1992), „Davenport – Schinzelova teorie matic“, Diskrétní matematika, 103 (3): 233–251, doi:10.1016 / 0012-365X (92) 90316-8, PAN 1171777.
- Kaiser, Tomáš; Klazar, Martin (březen 2002), „O tempech růstu uzavřených permutačních tříd“, Electronic Journal of Combinatorics, 9 (2): Research paper 10, 20, PAN 2028280.
- Klazar, Martin (2000), „Domněnka Füredi – Hajnal implikuje domněnku Stanley – Wilf“, Formální výkonové řady a algebraická kombinatorika (Moskva, 2000), Springer, str. 250–255, PAN 1798218.
- Klazar, Martin (2010), „Some general results in combineatorial enumeration“, Permutační vzorce, London Math. Soc. Přednáška Ser., 376, Cambridge: Cambridge Univ. Stiskněte, str. 3–40, doi:10.1017 / CBO9780511902499.002, PAN 2732822.
- Marcus, Adam; Tardos, Gábor (2004), „Vyloučené permutační matice a Stanleyho-Wilfova domněnka“, Journal of Combinatorial Theory, Řada A, 107 (1): 153–160, doi:10.1016 / j.jcta.2004.04.002, PAN 2063960.
- Vatter, Vincent (2010), „Permutační třídy každé míry růstu nad 2,48188“, Mathematika, 56 (1): 182–192, arXiv:0807.2815, doi:10.1112 / S0025579309000503, PAN 2604993.
- Vatter, Vincent (2011), „Malé permutační třídy“, Proc. London Math. Soc., Řada 3, 103 (5): 879–921, arXiv:0712.4006, doi:10.1112 / plms / pdr017, PAN 2852292.