Spelling suggestions: "subject:"ramsey assimétrico"" "subject:"ramsey simétrico""
1 |
Estructura y números de Ramsey para ciclos versus ruedas de tamaño imparSanhueza Matamala, Nicolás Ignacio January 2014 (has links)
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.
|
Page generated in 0.0657 seconds