← All problems

Prefix-exchange conjecture for increasing and decreasing patterns

23 years old · traced to

Let σ\sigma and τ\tau be patterns, and write σ∼Iτ\sigma\sim_{\mathcal{I}}\tau when they are equinumerous for avoidance by involutions, meaning that In(σ)=In(τ)\mathcal{I}_{n}(\sigma)=\mathcal{I}_{n}(\tau) for every nn. A prefix is an initial consecutive pattern such as 12…k12\ldots k or k…21k\ldots21. Prefix-exchange conjecture. For every kk, the prefixes 12…k12\ldots k and k…21k\ldots21 may be exchanged; equivalently,

12…k∼Ik…21.12\ldots k\sim_{\mathcal{I}}k\ldots21.

The conjecture extends the known results for short increasing and decreasing prefixes and would explain further pattern equivalences for involutions. Its general case is left open in the source.

References

Status

  • Solved: Mireille Bousquet-Melou and Einar Steingrimsson. Decreasing subsequences in permutations and Wilf equivalence for involutions (Journal of Algebraic Combinatorics 22, 383–409, 2005) https://arxiv.org/abs/math/0405334

Source: Aaron D. Jaggard, “Prefix exchanging and pattern avoidance by involutions”, arXiv:math/0306002 (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.