Universal Arrays

A word on q symbols is a sequence of letters from a fixed alphabet of size q. For an integer k⩾1, we say that a word w is k-universal if, given an arbitrary word of length k, one can obtain it by removing letters 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))cqk is k-universal with high probability, where cq is an explicit constant whose value is roughly qlog⁡q. Moreover, we show that the k-universality property for uniformly chosen words exhibits a sharp threshold. Finally, by extending techniques of Alon (2017) [1], we give asymptotically tight bounds for every higher dimensional analogue of this problem.