Equality characterization for the maximal Stanley–Wilf limit

A pattern qq of length kk is a permutation pattern, and let Sn(q)S_n(q) denote the number of permutations of length nn avoiding qq. Define its Stanley–Wilf limit by

L(q)=limnSn(q)n.L(q)=\lim_{n\to\infty}\sqrt[n]{S_n(q)}.

A pattern is layered if it is a direct sum of decreasing permutations. The strengthened Arratia conjecture. For every pattern qq of length kk,

L(q)(k1)2,L(q)\leq (k-1)^2,

with equality if and only if qq is layered or the reverse of qq is layered. The upper bound is known, while the stated if-and-only-if characterization is presented in the source as a conjectural strengthening and is not resolved there.

Sources & referencesView supporting material

Primary source

Miklos Bona, “The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns”, arXiv:math/0403502 (2004).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.