Matías Pavez-SignéQuiroz, DanielDanielQuirozNicolás Sanhueza-Matamala2025-12-062025-12-062021-09-2010.1016/j.disc.2021.1126262-s2.0-85115104242https://cris-uv-2.scimago.es/handle/123456789/7120WOS:000712876500027A 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.enacceso abiertoDiscrete Mathematics And CombinatoricsMathematicsTheoretical Computer Sciencearticle