The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns (Q556857): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / review text | |||
If \(p=p_1p_2\dots p_n\) and \(q\) are permutations of \(\{ 1,2,\dots,n\}\) and \(\{ 1,2,\dots,k\}\) for \(k\leq n\), respectively, then \(p\) is said to contain the pattern \(q\) if \(q\) and \(p_{i_1}p_{i_2}\dots p_{i_k}\) are order isomorphic for some \(1\leq i_1<i_2<\dots<i_k\leq n\), i.e. the terms are ordered in the same relative way. Let \(S_n(q)\) denote the number of permutations of \(\{ 1,2,\dots,n\}\) that do not contain a pattern \(q\). It follows from a recent result of Marcus and Tardos that the limit \(L(q)=\lim_{n\to\infty}(S_n(q))^{1/n}\) exists. In the present paper the author proves that \(L(12453)=9+4\sqrt{2}\) providing the first example of a pattern \(q\) for which \(L(q)\) is not an integer. He also determines \(L(q_k)\) for \(q_k=12\dots(k-3)(k-1)k(k-2)\) as \((k-4+\sqrt{8})^2\). Finally, he proves that \(L(q)\geq L(12\dots k)=(k-1)^2\) for so-called layered patterns \(q\) of length \(k\) which supports a conjecture from 1997 stating that \(S_n(q)\geq S_n(12\dots k)\) for such patterns \(q\). | |||
Property / review text: If \(p=p_1p_2\dots p_n\) and \(q\) are permutations of \(\{ 1,2,\dots,n\}\) and \(\{ 1,2,\dots,k\}\) for \(k\leq n\), respectively, then \(p\) is said to contain the pattern \(q\) if \(q\) and \(p_{i_1}p_{i_2}\dots p_{i_k}\) are order isomorphic for some \(1\leq i_1<i_2<\dots<i_k\leq n\), i.e. the terms are ordered in the same relative way. Let \(S_n(q)\) denote the number of permutations of \(\{ 1,2,\dots,n\}\) that do not contain a pattern \(q\). It follows from a recent result of Marcus and Tardos that the limit \(L(q)=\lim_{n\to\infty}(S_n(q))^{1/n}\) exists. In the present paper the author proves that \(L(12453)=9+4\sqrt{2}\) providing the first example of a pattern \(q\) for which \(L(q)\) is not an integer. He also determines \(L(q_k)\) for \(q_k=12\dots(k-3)(k-1)k(k-2)\) as \((k-4+\sqrt{8})^2\). Finally, he proves that \(L(q)\geq L(12\dots k)=(k-1)^2\) for so-called layered patterns \(q\) of length \(k\) which supports a conjecture from 1997 stating that \(S_n(q)\geq S_n(12\dots k)\) for such patterns \(q\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Dieter Rautenbach / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 2181974 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
permutation | |||
Property / zbMATH Keywords: permutation / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pattern | |||
Property / zbMATH Keywords: pattern / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2105493981 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0403502 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Wilf-equivalence for singleton classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3148849 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4821520 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Permutations avoiding certain patterns: The case of length 4 and some generalizations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On growth rates of closed permutation classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Excluded permutation matrices and the Stanley-Wilf conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Asymptotic values for degrees associated with strips of Young diagrams / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Restricted permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4344108 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:48, 10 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns |
scientific article |
Statements
The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns (English)
0 references
23 June 2005
0 references
If \(p=p_1p_2\dots p_n\) and \(q\) are permutations of \(\{ 1,2,\dots,n\}\) and \(\{ 1,2,\dots,k\}\) for \(k\leq n\), respectively, then \(p\) is said to contain the pattern \(q\) if \(q\) and \(p_{i_1}p_{i_2}\dots p_{i_k}\) are order isomorphic for some \(1\leq i_1<i_2<\dots<i_k\leq n\), i.e. the terms are ordered in the same relative way. Let \(S_n(q)\) denote the number of permutations of \(\{ 1,2,\dots,n\}\) that do not contain a pattern \(q\). It follows from a recent result of Marcus and Tardos that the limit \(L(q)=\lim_{n\to\infty}(S_n(q))^{1/n}\) exists. In the present paper the author proves that \(L(12453)=9+4\sqrt{2}\) providing the first example of a pattern \(q\) for which \(L(q)\) is not an integer. He also determines \(L(q_k)\) for \(q_k=12\dots(k-3)(k-1)k(k-2)\) as \((k-4+\sqrt{8})^2\). Finally, he proves that \(L(q)\geq L(12\dots k)=(k-1)^2\) for so-called layered patterns \(q\) of length \(k\) which supports a conjecture from 1997 stating that \(S_n(q)\geq S_n(12\dots k)\) for such patterns \(q\).
0 references
permutation
0 references
pattern
0 references
0 references