Topics in extremal and probabilistic combinatorics: trees and words

Abstract

En esta tesis se estudia una serie de problemas en combinatoria extremal y probabilista relacionados a árboles y palabras. En la primera parte de este trabajo se estudian qué condiciones debe cumplir un grafo para que contenga a todos los árboles de cierto tamaño. Se prueban una serie de resultados que combinan condiciones de grado mínimo y máximo para contener a todos los árboles de cierto tamaño y grado acotado. También se logra un avance en la conjetura de Erdos Sós [42] para árboles de grado acotado. Finalmente, se estudia el problema de contenimiento de árboles en el grafo aleatorio G(n, p). Se prueba que incluso después de borrar una fracción de las aristas de G(n, p) el grafo resultante sigue conteniendo árboles grandes con grado acotado. En la segunda parte de esta tesis se estudian problemas extremales para palabras. Se determina el largo mínimo que debe tener una palabra para contener cada palabra de largo k. Además, se determina el umbral n = n(k) de modo que, con alta probabilidad, una palabra aleatoria de largo (1 + o(1))n contenga una copia de cada palabra de largo k. Finalmente, se estudia una noción de cuasi-aleatoriedad para palabras y se muestra una serie de propiedades equivalentes. Basados en esta noción de cuasi-aleatoriedad, se desarrolla una teoría límite para palabras finitas en el espíritu de lo que se ha hecho para grafos [82].