El lema de regularidad de Szemerédi y el problema de Erdös y Rothschild
Fecha
2020-01
Autores
Profesor Guía
Formato del documento
Tesis
ORCID Autor
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad de Valparaíso
Ubicación
ISBN
ISSN
item.page.issne
item.page.doiurl
Facultad
Facultad de Ciencias
Departamento o Escuela
Instituto de Matematicass
Determinador
Recolector
Especie
Nota general
Magíster en Matemáticas
Resumen
Esta tesis se centra en el estudio de aspectos fundamentales de la combinatoria extremal clásica y moderna. El objetivo principal es mostrar el tipo de preguntas y resultados de la combinatoria extremal, así como también algunas de las técnicas importantes en el desarrollo de ésta área.
Dividimos este trabajo en dos partes. En la primera parte, presentamos nociones básicas y algunos de los principales resultados de la teoría extremal de grafos. Mostramos dos de los teoremas más importantes de esta área, el Teorema de Turán y su generalización, el Teorema de Erdo˝ s-Stone. El Teorema de Turán afirma que la máxima cantidad de aristas que puede tener un grafo en n vértices sin contener un subgrafo completo en r + 1 vértices, denotado por Kr +1, está dada por la cantidad de aristas de un grafo r -partito, completo y balanceado, este último denotado por Tr (n) y su can-tidad de aristas por tr (n). Además el único grafo que alcanza tr (n) aristas es Tr (n). La generalización aproximada de este resultado es el Teorema de Erdo˝ s-Stone, en el cual en vez de prohibir grafos completos se prohiben grafos en general. Más precisamente, se tiene que dado cualquier H, la máxima cantidad posible de aristas que puede tener un grafo en n vértices sin contener H como subgrafo está dada por tχ(H )−1(n) + o(n² ), en donde χ(H ) corresponde al número cromático de H . Luego, introducimos una de las herramientas más poderosas y revolucionarias de la combinatoria extrema, el Lema de Regularidad de Szemerédi. A grandes rasgos, este importante resultado dice que todos los grafos se pueden particionar en una cantidad constante de partes de manera que las aristas entre la mayoría de las partes se comportan bien. Concluimos esta primera parte ilustrando el uso del Lema de Regularidad de Szemerédi en la demostración del Teorema de Roth, el Teorema de Erdo˝ s-Stone y también, en la demostración del Teorema de Estabilidad de Simonovits dada por Füredi [14].
En la segunda parte de este trabajo estudiaremos un problema planteado por Er- do˝ s y Rothschild: dados enteros n, k y r , ¿cuál es la máxima cantidad de k -arista- coloraciones que un grafo en n vértices puede alcanzar sin contener una copia monocromática de Kr +1?. A esta cantidad la denotamos por F (n, k , r + 1). Además, ¿qué grafos alcanzan F (n, k , r + 1)?. Una cota inferior trivial para F (n, k , r + 1) está dada por todas las k -arista-coloraciones de Tr (k ), pues Tr (k ) no contiene copias de Kr +1 como subgrafo. En este trabajo revisaremos dos artículos relacionados a este problema, que describimos a continuación. Inicialmente Erdo˝ s y Rothschild conjeturaron que F (n, 2, 3) = 2t2 (n) y que el único grafo que alcanza este valor es T2(n), el grafo bipartito, completo y balanceado. Yuster [25] probó que esta conjetura es cierta. Además, utilizando el Lema de Regularidad de Szemerédi demostró que F (n, 2, r + 1) es asintóticamente igual a 2tr (n) y conjeturó que F (n, 2, r + 1) = 2tr (n) para n suficientemente grande. Luego, Alon et al. [1] comprobaron la conjetura de Yuster y además probaron que F (n, 3, r +1) = 3tr (n) para n suficientemente grande y que el único grafo que alcanza este valor es Tr (n) el grafo en n vértices, r -partito, completo y balanceado.
Descripción
Lugar de Publicación
Auspiciador
Palabras clave
LOGICA COMBINATORIA