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

ISBN

ISSN

item.page.issne

Departamento o Escuela

CIMFAV

Determinador

Recolector

Especie

Nota general

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

Licencia

URL Licencia