Problemas do tipo Erdős-Rothschild para grafos - Marzo, Matheus Micadei (2024)
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.