Problemas do tipo Erdős-Rothschild para grafos

Abstract

Esta tese aborda diversos problemas do tipo Erdős-Rothschild, com o foco principal sendo a família de padrões localmente arco-íris com um determinado número mínimo de cores. O trabalho demonstra que, para um número fixo de cores distintas s e um número suficientemente grande de cores r, o grafo de Turán Tk(n) é a única estrutura que maximiza o número de colorações livres de padrões localmente arcoíris com pelo menos s cores. Isso significa que o grafo de Turán é o único grafo extremal para o problema proposto. Para chegar a essa conclusão, a tese emprega o método da estabilidade, que mostra que se um grafo tem um número de colorações livres de KLR k+1(s) maior ou igual a Tk(n), então esse grafo precisa ter uma estrutura próxima à do grafo de Turán, com poucas arestas internas em relação a alguma partição em k partes. A conclusão, como enunciada no parágrafo anterior, segue por um resultado que conhecemos por resultado exato. A demonstração da estabilidade para KLR k+1(s) envolve o uso do Lema da Regularidade de Szemerédi e lemas de imersão, que garantem a existência de padrões proibidos em colorações de grafos com base em sua estrutura. A tese também desenvolve algoritmos para construir colorações localmente arco-íris em situações específicas, o que é crucial para a prova dos lemas de imersão.

This thesis addresses several problems of the Erdős-Rothschild type, focusing primarily on the family of locally rainbow patterns with at least a given number of distinct colors. The work demonstrates that, for a fixed number of distinct colors s and a sufficiently large number of colors r, the Turán graph Tk(n) is the unique structure that maximizes the number of colorings avoiding locally rainbow patterns with at least s colors. This means that the Turán graph is the only extremal graph for the proposed problem. To reach this conclusion, the thesis employs the stability method, which shows that if a graph has a number of colorings free of KLR k+1(s) greater than or equal to Tk(n), then this graph must be structurally similar to the Turán graph, with few internal edges with respect to a partition into k parts. The conclusion, as stated in the previous paragraph, follows from a result we know as the exact result. The proof of stability for KLR k+1(s) involves the use of Szemerédi’s Regularity Lemma and embedding lemmas, which guarantee the existence of forbidden patterns in graph colorings based on their structure. The thesis also develops algorithms to construct locally rainbow colorings in specific situations, which is crucial for proving the embedding lemmas.