Three Problems Involving Permutations

We study three problems involving permutations: the n-card problem, inv-Wilf-equivalence, and suitable sets of permutations. The n-card problem is to determine the minimal intervals [u, v] such that for every n times n stochastic matrix A there is an n times n permutation matrix P (depending on A) such that tr(PA) belongs to [u, v]. The minimal intervals for the n-card problem are known only for n <= 4. We answer a question posed by Sands, by showing that [1, 2] is a solution to the n-card problem for all n >= 2. We also show that each closed interval of length n/(n−1) contained in [0, 2) is a solution to the n-card problem for all n >= 2. Wilf-equivalence is one of the central concepts of pattern-avoiding permutations. The two known infinite families of Wilf-equivalent permutation pairs both satisfy the stronger condition of shape-Wilf-equivalence. Dokos et al. studied a different strengthening of Wilf-equivalence called inv-Wilf-equivalence. They conjectured that all inv-Wilf-equivalent permutation pairs arise from trivial symmetries. We disprove this conjecture with an infinite family of counterexamples, obtained by generalizing simultaneously the concepts of shape-Wilf-equivalence and inv-Wilf-equivalence. We also prove the Baxter-Jaggard conjecture on even-shape-Wilf-equivalent permutation pairs. A set of N permutations of {1, 2, . . . , v} is (N, v, t)-suitable if each symbol precedes each subset of t − 1 others in at least one permutation. We give examples of suitable sets of permutations for new parameter triples (N, v, t). We relate certain suitable sets of permutations with parameter t to others with parameter t + 1, thereby showing that one of the two infinite families presented by Colbourn can be constructed directly from the other. We prove an exact nonexistence result for suitable sets of permutations using elementary combinatorial arguments. We then establish an asymptotic nonexistence result using Ramsey’s theorem.