Title: Metades esparsas em grafos livres de triângulos
Data: 30 de outubro de 2024 – 4a feira – 14h - Auditório Jacy Monteiro
Student: César Augusto Bispo dos Santos

Abstract: Erd\H{o}s conjecturou que todo grafo livre de triângulos com $n$ vértices contém um subconjunto de $\floor{n/2}$ vértices que induz no máximo $n^2/50$ arestas. Krivelevich confirmou essa conjectura para grafos com $n$ vértices e grau mínimo pelo menos $2n/5$ e Keevash e Sudakov melhoraram esse resultado, estendendo-o para grafos com grau médio pelo menos $2n/5$.

Norin e Yepremyan reforçaram a conjectura de Erd\H{o}s para grafos $G$ com $\delta(G) \geq 5n/14$ e também para grafos com grau médio pelo menos $(2n/5 - \gamma)n$ para algum $\gamma > 0$. Estendendo esse resultado, Bedenknecht, Mota, Reiher e Schacht confirmaram a conjectura para grafos homomorfos a grafos de Andrásfai. Como consequência, segue que a conjectura é válida para grafos livres de triângulos com grau mínimo maior que $10n/29$. Eles também obtiveram um resultado mais geral para grafos de cintura ímpar alta. Se a conjectura for verificada para uma família conhecida como grafos Vega, então sabe-se que é válida para todo grafo $G$ com $\delta(G) > n/3$. Neste mestrado, realizamos um estudo aprofundado sobre o problema, apresentando alguns dos resultados discutidos acima e dois resultados originais que contribuem para o avanço em direção à solução da conjectura para grafos homomorfos a grafos Vega.