Universal permutations

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.

Comments: