Teoría de Ramsey para árboles: el caso de la doble estrella
Professor Advisor
dc.contributor.advisor
Stein, Maya
Author
dc.contributor.author
Flores Dubó, Freddy Ignacio
Associate professor
dc.contributor.other
Kiwi Krauskopf, Marcos
Associate professor
dc.contributor.other
Matamala Vásquez, Martín
Associate professor
dc.contributor.other
Quiroz Brito, Daniel
Admission date
dc.date.accessioned
2021-06-11T22:09:43Z
Available date
dc.date.available
2021-06-11T22:09:43Z
Publication date
dc.date.issued
2021
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/180109
General note
dc.description
Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas
es_ES
General note
dc.description
Memoria para optar al título de Ingeniero Civil Matemático
Abstract
dc.description.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.
es_ES
Patrocinador
dc.description.sponsorship
CMM ANID PIA AFB170001, Fondecyt Regular 1183080 y por la Escuela de Ingeniería y Ciencias, FCFM, Universidad de Chile