Aluno: Marcelo Machado Lage
Orientador: Prof. Dr. Guilherme Oliveira Mota
Título: Sobre uma conjectura de Erdős acerca de grafos livres de triângulos
Grafos livres de triângulos são objetos de grande importância na Teoria Extremal dos Grafos. O clássico Teorema de Mantel mostra o limite para o número máximo de arestas que um tal grafo pode ter, e, a partir da década de 1960, perguntas mais desafiadoras vêm sendo postas relacionadas a grafos livres de triângulos. Nesse trabalho, investigamos questões de estabilidade em grafos livres de triângulos e, particularmente, uma conjectura proposta por Erdős em 1975 sobre a distância entre grafos livres de triângulos e grafos bipartidos.
Inicialmente, apresentamos resultados parciais para a conjectura utilizando técnicas clássicas em Teoria Extremal dos Grafos. Em seguida, apresentamos duas técnicas modernas que têm sido usadas para avançar em conjecturas sobre grafos livres de triângulos: as álgebras de flag de Razborov, que permitem automatizar certas estratégias de prova que generalizam os métodos clássicos usando cortes locais; teoremas de homomorfismos em grafos com restrição de grau mínimo, que facilitam o estudo de objetos complexos a partir de uma perspectiva mais simples. Por fim, obtemos avanços parciais na conjectura principal utilizando esses dois métodos, que se complementam pela força expressiva e versatilidade computacional das álgebras de flag e pela simplificação estrutural dos teoremas de homomorfismos.