Pavez-Signé, MatíasQuiroz, Daniel A.Sanhueza-Matamala, Nicolás2022-11-302022-11-302021http://repositoriobibliotecas.uv.cl/handle/uvscl/7488A word on q symbols is a sequence of letters from a fixed alphabet of size q. For an integer , 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 is k-universal with high probability, where is an explicit constant whose value is roughly . 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.UNIVERSAL STRUCTUREARRAYWORDUNIFORMLY CHOSENSUBWORD MATRIXArticulohttps://doi.org/10.1016/j.disc.2021.112626