Árboles y caminos en subgrafos aleatorios de torneos

Abstract

El presente trabajo define un modelo de subgrafos aleatorios de torneos $T_{p}$ y desarrolla técnicas que combinan ideas de grafos aleatorios, de torneos y de teoría extremal para encontrar ciertas familias de subestructuras en $T_{p}$ con alta probabilidad.\\

A lo largo del trabajo se demuestra la aparición de caminos y árboles orientados de tamaño lineal, con grado máximo y altura acotados, en el grafo orientado aleatorio $T_{p}$, para todo torneo $T$, y todo $p$ suficientemente grande. Esto sienta un precedente sobre las clases de estructuras que es posible encontrar en subgrafos aleatorios de torneos $T_{p}$.\\

Se analiza también el largo máximo de un camino dirigido $T_{p}$ que aparece con alta probabilidad, y se verifica que para todo $T$, es de al menos tamaño $\frac{np}{4}$, para todo $0\leq p\leq 1$.\\