Elizalde–Noy maximality conjecture for consecutive pattern avoidance

About 19 years old · traced to

Let SkS_k denote the set of permutations of length kk, and let αp(n)\alpha_p(n) be the number of permutations of length nn avoiding the consecutive pattern pp. For a fixed pattern length kk, write

σ=12…k.\sigma=1 2 \ldots k.

Elizalde–Noy maximality conjecture. The increasing pattern σ\sigma is the maximal pattern, in the sense that

ασ(n)≥αp(n)\alpha_{\sigma}(n) \geq \alpha_p(n)

for all p∈Skp\in S_k and all nn. This conjecture concerns the extremal enumeration of consecutive pattern avoidance; the source attributes it to Elizalde and Noy and gives no resolution.

References

Primary source

Brian Nakamura, “Computational Approaches to Consecutive Pattern Avoidance in Permutations”, arXiv:1102.2480 (2011).

Additional references

2 papers in this index state this conjecture (2007–2011). The statement above is taken from the most recent of them; the others are arXiv:0711.4325.

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.