Ingeniero Civil Matemático / Un coloreo de aristas de un grafo se llama γ-promedio si es que el número promedio de colores incidentes a cada vértice es a lo más γ. Dados n, m enteros positivos y γ un real positivo, el número de Turán promedio coloreado T(n, K_m, γ-promedio) corresponde a la máxima cantidad de aristas que puede tener un grafo de n vértices de manera que exista un coloreo γ-promedio que no contenga ninguna copia monocromática de K_m. Esta noción fue introducida por Caro, quien observa que la expansión (blow-up) de un grafo completo γ-promedio coloreado sin copias monocromáticas de K_m también es γ-promedio coloreado y tampoco posee copias monocromáticas de K_m. Con ello, Caro se pregunta de si el máximo de aristas buscado se alcanza en la expansión de un grafo completo γ-promedio coloreado que maximice el número de vértices bajo la condición de no contener una copia monocromática de K_m (un coloreo extremal para el número de Ramsey γ-promedio).
Yuster probó que la respuesta es afirmativa para el caso m=3 y γ=2, y además conjeturó que la respuesta es siempre afirmativa para todos los γ = ℓ ∈ N. En la presente memoria se demuestra esta conjetura de Yuster cuando m >= ℓ(ℓ+1)+1. Por otro lado, se demuestra también que la respuesta a la pregunta de Caro es negativa para un conjunto no numerable de valores de γ ∉ N.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/146758 |
| Date | January 2017 |
| Creators | Piga Díaz, Simón Cristóbal |
| Contributors | Stein, Maya, Han, Hiep, Matamala Vásquez, Martín |
| 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.0021 seconds