Ingeniero Civil Matemático / 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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/117105 |
| Date | January 2014 |
| Creators | Sanhueza Matamala, Nicolás Ignacio |
| Contributors | Stein, Maya, Facultad de Ciencias Físicas y Matemáticas, Departamento de Ingeniería Matemática, Matamala Vásquez, Martín, Soto San Martín, José |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0018 seconds