El lema de regularidad de Szemerédi y el problema de Erdös y Rothschild

Vista sencilla de ítem
dc.contributor.advisorJiménez Ramírez, Andrea
dc.contributor.authorSaavedra Herrera, Angelo
dc.date.accessioned2023-11-27T18:31:13Z
dc.date.available2023-11-27T18:31:13Z
dc.date.issued2020-01
dc.description.abstractEsta 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.en_ES
dc.facultadFacultad de Cienciasen_ES
dc.identifier.citationSaavedra, A. (2020). El lema de regularidad de Szemerédi y el problema de Erdös y Rothschild (Tesis de postgrado). Universidad de Valparaíso, Valparaíso, Chile.en_ES
dc.identifier.urihttps://repositoriobibliotecas.uv.cl/handle/uvscl/13398
dc.language.isoesen_ES
dc.publisherUniversidad de Valparaísoen_ES
dc.subjectLOGICA COMBINATORIAen_ES
dc.titleEl lema de regularidad de Szemerédi y el problema de Erdös y Rothschilden_ES
dc.typeTesisen_ES
uv.catalogadorPJR CIENen_ES
uv.departamentoInstituto de Matematicassen_ES
uv.notageneralMagíster en Matemáticasen_ES

Archivos

Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
El tema de regularidad de Szemerédi y el problema de Erdös y Rothschild.pdf
Tamaño:
497.2 KB
Formato:
Adobe Portable Document Format
Descripción:
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
384 B
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar

Colecciones

Tesis