  A word on $q$ symbols is a sequence of letters from a fixed alphabet of size
$q$. For an integer $k\ge 1$, we say that a word $w$ is $k$-universal if, given
an arbitrary word of length $k$, one can obtain it by removing entries from
$w$. It is easily seen that the minimum length of a $k$-universal word on $q$
symbols is exactly $qk$. We prove that almost every word of size $(1+o(1))c_qk$
is $k$-universal with high probability, where $c_q$ is an explicit constant
whose value is roughly $q\log q$. Moreover, we show that the $k$-universality
property for uniformly chosen words exhibits a sharp threshold. Finally, by
extending techniques of Alon [Geometric and Functional Analysis 27 (2017), no.
1, 1--32], we give asymptotically tight bounds for every higher dimensional
analogue of this problem.
