Problemas do tipo Erdős-Rothschild para grafos

• Ano de defesa: 2024
• Autor(a) principal: Marzo, Matheus Micadei
• Orientador(a): Hoppen, Carlos
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Grafos; Teoria extremal de grafos; Coloração; Arco-iris; Lema de regularidade de Szemerédi
• Link de acesso: http://hdl.handle.net/10183/280491

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.