Albert–Atkinson conjecture on layered patterns maximizing avoidance

Let Sn(q)S_n(q) denote the number of permutations of length nn that avoid a pattern qq. A pattern is layered if it consists of decreasing subsequences whose entries increase from one layer to the next. Let qq be a non-layered pattern of length kk, and let QQ be a layered pattern of length kk. Layered-pattern maximality conjecture. For every positive integer nn,

Sn(q)Sn(Q).S_n(q)\leq S_n(Q).

If true, bounds for layered patterns would give bounds for all patterns of the same length. Numerical evidence supports the conjecture, but the general assertion remains open.

Sources & referencesView supporting material

Primary source

Miklos Bona, “On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length”, arXiv:1209.2404 (2012).

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.