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.

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.