On Square Permutations

摘要

Given permutations π and σ_1, and σ_2, the permutation π is said to be a shuffle of σ_1 and σ_2, in symbols π ∈ σ_1 • σ_2, if π (viewed as a string) can be formed by interleaving the letters of two strings p_1 and p_2 that are order-isomorphic to σ_1 and σ_2, respectively. In case σ_1 = σ_2, the permutation π is said to be a square and σ_1 = σ_2 is a square root of n. For example, π = 24317856 is a square as it is a shuffle of the patterns 2175 and 4386 that are both order-isomorphic to σ = 2143 as shown in π = ~2_(43)~(17)_8~5_6. However, σ is not the unique square root of n since π is also a shuffle of patterns 2156 and 4378 that are both order-isomorphic to 2134 as shown in π = ~2_(43)~1_(78)~(56). We shall begin by presenting recent results devoted to recognizing square permutations and related concepts with a strong emphasis on constrained oriented matchings in graphs. Then we shall discuss research directions to address square permutation challenges in both combinatorics and algorithmic fields.