Tìtulo: “Un estudio experimental de la discrepancia mínima de secuencias de de Bruijn”
Directores: Nicolás Álvarez y Verónica Becher
Jurados:Martín Mereb y Pablo Turjanski

Resumen:
Una secuencia de de Bruijn de orden n con dos símbolos es una secuencia circular de longitud 2^n en la que cada bloque de nn símbolos consecutivos aparece exactamente una vez. La discrepancia de bloque mide el desbalance que tiene una secuencia. Se define considerando todas las subsecuencias contiguas de cualquier longitud: para cada longitud de bloque, se mira la diferencia entre el bloque que más aparece y el que menos aparece; luego se toma el máximo de esas diferencias entre todas las longitudes posibles. La tesis encuentra experimentalmente que, para n ≤ 8, la menor discrepancia alcanzable es nn, que es el valor mínimo teórico. Además, muestra que existen secuencias de de Bruijn con esa discrepancia mínima que admiten una descomposición en exactamente 4 ciclos disjuntos en el grafo de de Bruijn, y que también se pueden construir a partir de dos secuencias de de Bruijn de orden menor, ambas con discrepancia mínima.