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 |
Changed an Item |
||
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 |
Revision as of 14:55, 1 July 2023
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