# 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:

**None**:

**2013-03-03T16:38:09Z**

This reminds me of Ran Raz's paper "VC-DIMENSION OF SETS OF PERMUTATIONS" published in

*Combinatorica*in 2000.

**11011110**:

**2013-03-03T16:53:33Z**

Thanks, I'll have to look that up.

**None**:

**2013-03-04T15:01:47Z**

Check out: Miller, Alison Asymptotic bounds for permutations containing many different patterns.

*J. Combin. Theory*Ser. A 116 (2009), no. 1, 92–108.

**11011110**:

**2013-03-04T16:02:29Z**

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.