Teoría de Ramsey para árboles: el caso de la doble estrella

Abstract

Una doble estrella $S(n,m)$ es el grafo obtenido a partir de una estrella con $n$ hojas y otra estrella con $m$ hojas al unir sus centros con una arista. Sea $R(S(n,m))$ el número de Ramsey, definido como el mínimo $N$ tal que existe una copia monocromática de $S(n,m)$ en cualquier dos coloreo de las aristas del grafo completo en $N$ vértices. Se prueba que para constantes $\delta$, $\beta$ que satisfacen ciertas restricciones, se tiene que para todo $m\geq 0$ $$R(S(\delta m,m)) \leq (2\delta-\beta +0.4)m+1.$$ En particular, obtenemos una cota superior para $R(S(2m,m))$, que responde parcialmente una pregunta hecha por Norin, Sun y Zhao en el año 2016. Luego, se muestra la estructura general del coloreo del grafo completo en $4.35m+1$ vértices que no posee la doble estrella $S(2m,m)$ monocromática. Esto último con la intención de sentar las bases para trabajo futuro que responda completamente la pregunta de Norin, Sun y Zhao.