Universal arrays
Fecha
2021
Profesor Guía
Formato del documento
Articulo
ORCID Autor
Título de la revista
ISSN de la revista
Título del volumen
Editor
Elsevier
Ubicación
ISBN
ISSN
item.page.issne
item.page.doiurl
Facultad
Facultad de Ingeniería
Departamento o Escuela
CIMFAV
Determinador
Recolector
Especie
Nota general
No disponible para descarga
Resumen
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.
Descripción
Lugar de Publicación
Auspiciador
Palabras clave
UNIVERSAL STRUCTURE, ARRAY, WORD, UNIFORMLY CHOSEN, SUBWORD MATRIX