Problemas do tipo Erdős-Rothschild para grafos

Detalhes bibliográficos
Ano de defesa: 2024
Autor(a) principal: Marzo, Matheus Micadei
Orientador(a): Hoppen, Carlos
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/10183/280491
Resumo: 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.