The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns

Abstract: We show the first known example for a pattern

q

for which

l i m_{n o i n f t y} s q r t [n] S_{n} (q)

is not an integer. We find the exact value of the limit and show that it is irrational. Then we generalize our results to an infinite sequence of patterns. Finally, we provide further generalizations that start explaining why certain patterns are easier to avoid than others. Finally, we show that if

q

is a layered pattern of length

k

, then

L (q) g e q (k - 1)^{2}

holds.

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\).

Recommendations

Cites work

Cited in

(16)

This page was built for publication: The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q556857)