Let's say that a permutation on the numbers from \( 1 \) to \( n \) is \( k \)-universal if its subsequences of \( k \) items have all of the \( k! \) possible different patterns that they could have. For instance, 25314 is 3-universal: the six possible patterns 123, 132, 213, 231, 312, and 321 appear in it as 234, 253, 314, 231, 514, and 531 respectively. How short can a \( k \)-universal pattern be?
It's not hard to find upper and lower bounds within a constant factor of each other. In one direction, the sequence \[ k, 2k, 3k, \dots k-1, 2k-1, 3k-1, \dots, k-2, 2k-2, 3k-2, \dots \] etc of length \( k^2 \) is universal. (This is the same tilted grid pattern that gives the lower bound in the Erdős–Szekeres theorem.) In the other direction, the length \( n \) of the universal permutation must be at least some constant times \( k^2, \) in order for it to have at least \( k! \) different subsets of size \( k. \) But what is the constant?
A computer search found that there is no 4-universal permutation on 8 items (the best is 51862473 which has 23 out of the 24 possible patterns), but the 9-item permutation 162975384 is universal. So the sequence of lengths of the shortest \( k \)-universal patterns begins 1, 3, 5, 9, ... But although there are simple quadratically-growing sequences like \( \lceil (k^2+1)/2 \rceil \) that begin like this, it's not really long enough to identify this in OEIS and see whether it matches anything known.
This reminds me of Ran Raz's paper "VC-DIMENSION OF SETS OF PERMUTATIONS" published in Combinatorica in 2000.
Thanks, I'll have to look that up.
Check out: Miller, Alison Asymptotic bounds for permutations containing many different patterns. J. Combin. Theory Ser. A 116 (2009), no. 1, 92–108.
Extremely relevant, thanks! So thanks to this reference I now know that there exist \( k \)-universal permutations of size \( k(k+1)/2 \) and that it's conjectured that the leading constant of this expression cannot be improved.