Maximal avoidance conjecture for the patterns M2m−1M_{2m-1} and M2mM_{2m}

About 14 years old · traced to

Let Sn(q)S_n(q) denote the number of permutations of length nn that avoid a pattern qq. For m≥2m\geq 2, define M2mM_{2m} to be the pattern 132⋯(2m−1)(2m−2)2m132\cdots(2m-1)(2m-2)2m, and define M2m−1M_{2m-1} to be the pattern obtained from M2mM_{2m} by removing its first entry and relabeling; thus M2m−1=21⋯(2m−2)(2m−3)(2m−1)M_{2m-1}=21\cdots(2m-2)(2m-3)(2m-1). Maximal-MM conjecture. For every m≥2m\geq 2, both of the following hold: (A) for every positive integer nn and every pattern qq of length 2m−12m-1,

Sn(q)≤Sn(M2m−1);S_n(q)\leq S_n(M_{2m-1});

and (B) for every positive integer nn and every pattern qq of length 2m2m,

Sn(q)≤Sn(M2m).S_n(q)\leq S_n(M_{2m}).

This is a stronger, parity-specific version supported by numerical evidence of the conjecture that layered patterns maximize the number of avoiding permutations. Its general validity remains open.

References

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.