Estructura y números de Ramsey para ciclos versus ruedas de tamaño impar
Professor Advisor
dc.contributor.advisor
Stein, Maya
Author
dc.contributor.author
Sanhueza Matamala, Nicolás Ignacio
Staff editor
dc.contributor.editor
Facultad de Ciencias Físicas y Matemáticas
Staff editor
dc.contributor.editor
Departamento de Ingeniería Matemática
Associate professor
dc.contributor.other
Matamala Vásquez, Martín
Associate professor
dc.contributor.other
Soto San Martín, José
Admission date
dc.date.accessioned
2014-10-09T20:31:38Z
Available date
dc.date.available
2014-10-09T20:31:38Z
Publication date
dc.date.issued
2014
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/117105
General note
dc.description
Ingeniero Civil Matemático
Abstract
dc.description.abstract
Se estudia la estructura de grafos completos de tamaño apropiado, con una coloreación de sus aristas en dos colores, de manera tal que no presentan como subgrafos monocromáticos a ciertos tipos de grafos específicos. En este caso se considera el caso de un ciclo impar C_n con n vértices y una rueda W_n := K_1 + C_n con n+1 vértices; en el caso en que n es impar.
Se muestra que para n impar y todo grafo completo de tamaño apropiado, con una coloreación de sus aristas en azul y rojo que no contenga como subgrafo monocromático rojo a C_n ni como subgrafo monocromático azul a W_n; eliminando a lo más dos vértices se obtiene una partición de sus vértices en tres conjuntos que inducen grafos completos de color rojo, y aristas formando un grafo tripartito completo.
Dicho resultado se puede ver como una generalización de resultados presentados por Nikiforov y Schelp; y como una suerte de recíproca a cotas conocidas para números de Ramsey asimétricos.
Como resultado secundario de la demostración se obtienen dos cotas para el número de Ramsey de r(C_{2k+1}, W_{2k+2}): una es más fina para valores pequeños de k y la otra es mejor en el caso asintótico. Los valores exactos de dichos números de Ramsey son, en este instante, un problema abierto. Las cotas expresadas son una aproximación a los valores que han sido conjeturados y permiten ver que, al menos a un nivel asintótico, dichos resultados son ciertos.