Additional Problem 12: Short Superpatterns of Permutations (Preliminary version)

We can treat a permutation $\pi$ as a permutation pattern, it matches every word order-equivalent to $\pi$ (see Problem 31). The aim here is to build a short word, called superpattern, such that each $n$-permutation is order-equivalent to its subsequence. We are interested in superpatterns having $n+1$ letters $\{1,2,\ldots,n+1\}$. Define $\alpha_n$ as increasing sequence of all odd letters, and $\beta_n$ as decreasing sequence of even letters. Define also $$Z_n= \cases{ (\alpha_n\,\beta_n)^{n/2} & if n even\cr (\alpha_n\,\beta_n)^{\lfloor n/2 \rfloor}\,\alpha_n & otherwise. }$$

We have $|Z_n|=(n^2+n)/2$. Observe that the supersequence constructed in Problem 15 is almost twice larger.

Compute in linear time an order-preserving embedding of a given permutation $\pi$ of size $n$ into $Z_n$.

References

• Miller, A, Asymptotic bounds for permutations containing many different patterns, J. Combin. Theory Ser. A. 116(1) (2009) 92-108. DOI: 10.1016/j.jcta.2008.04.007.