Universal arrays

dc.contributor.author	Pavez-Signé, Matías
dc.contributor.author	Quiroz, Daniel A.
dc.contributor.author	Sanhueza-Matamala, Nicolás
dc.date.accessioned	2022-11-30T02:46:46Z
dc.date.available	2022-11-30T02:46:46Z
dc.date.issued	2021
dc.description.abstract	A 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.	en_ES
dc.facultad	Facultad de Ingeniería	en_ES
dc.file.name	Pavez_Uni2021.pdf
dc.identifier.doi	https://doi.org/10.1016/j.disc.2021.112626
dc.identifier.uri	http://repositoriobibliotecas.uv.cl/handle/uvscl/7488
dc.language	en
dc.publisher	Elsevier
dc.source	Discrete Mathematics
dc.subject	UNIVERSAL STRUCTURE	en_ES
dc.subject	ARRAY	en_ES
dc.subject	WORD	en_ES
dc.subject	UNIFORMLY CHOSEN	en_ES
dc.subject	SUBWORD MATRIX	en_ES
dc.title	Universal arrays
dc.type	Articulo
uv.departamento	CIMFAV
uv.notageneral	No disponible para descarga

Archivos

Mostrando 1 - 1 de 1