Proposta de trabalho

Introdução e motivação

Um grafo (não dirigido, simples e finito) \(G\) é chamado de livre de triângulos se não existem três vértices distintos \(x,y,z\) em \(V(G)\) tais que \(xy,yz,zx \in E(G)\).

Em 1907, Mantel provou que um grafo livre de triângulos tem no máximo \(n^2/4\) arestas. Em 1955, Mycieslki deu uma construção para grafos livres de triângulos com número cromático arbitrariamente grande. Em 2006, 50 anos depois de Mantel, grafos livres de triângulos ainda eram objeto de grande estudo, com Brandt e Thomassé provando que todo grafo livre de triângulos com \(n\) vértices e grau mínimo maior que \(n/3\) tem número cromático no máximo 4. Em 2011, um conjunto de autores, incluindo A. Razborov, determinou a quantidade máxima de pentágonos que um grafo livre de triângulos pode ter utilizando o formalismo moderno das flag algebras.

Grafos livres de triângulos têm sido objeto de estudo contínuo há mais de 100 anos, e uma série de problemas importantes permanece em aberto sobre essa classe de grafos.

Dois problemas de Erdős

Em 1976, Erdős conjecturou os seguintes resultados:

(Sparse Half Conjecture) Seja \(G\) um grafo livre de triângulos com \(n\) vértices. Então existe um conjunto de vértices de \(G\) com tamanho \(n/2\) que determina entre si no máximo \(n^2/50\) arestas.
(Make Bipartite Conjecture) Seja \(G\) um grafo livre de triângulos com \(n\) vértices. Então \(G\) pode ser transformado em um grafo bipartido deletando no máximo \(n^2/25\) arestas.

O que faremos

Nesse trabalho, iremos estudar as técnicas utilizadas no segundo problema e explorar novos caminhos para avanços em ambos os problemas, considerando (ou não) restrições de grau mínimo aos grafos.

Isso será feito estudando artigos selecionados da vasta literatura existente sobre grafos livres de triângulos, com reuniões frequentes entre o aluno e o orientador para investigar novos métodos e resultados e eventuais discussões com outros pesquisadores, vinculados ao IME-USP ou a outras instituições.

Além dessas reuniões, propomos o seguinte cronograma para atividades específicas da disciplinas, que poderá sofrer alterações ao longo da realização do trabalho mas servirá como base nesse primeiro momento.

Cronograma de atividades

Atividade	Abr	Mai	Jun	Jul	Ago	Set	Out	Nov	Dez
Seleção e estudo das referências básicas
Seleção e estudo de artigos específicos
Escrita da monografia
Revisão, elaboração do pôster e entrega final

Referências

Como primeiros passos, revisaremos algumas referências básicas sobre o problema, os grafos de Andrásfai e os grafos Vega. Assim, será adquirida maior familiaridade com os resultados existentes para os problemas, técnicas de imersão e homomorfismo de grafos utilizadas quando restrições de grau mínimo estão em jogo.

W. Bedenknecht; G. O. Mota; C. Reiher; M. Schacht. On the local density problem for graphs of given odd‐girth
J. Balogh; F. C. Clemen; B. Lidický. 10 Problems for Partitions of Triangle-free Graphs
T. Łuczak; J. Polcyn; C. Reiher. Andrásfai and Vega graphs in Ramsey-Turán theory
T. Łuczak; J. Polcyn; C. Reiher. The next case of Andrásfai's conjecture
L. E. Z. Fernández. Densidade local em grafos (tese de doutorado)
M. Krivelevich. On the Edge Distribution of Triangle-free Graphs

Em paralelo, a perspectiva histórica do problema deverá ser estudada, observando as técnicas estruturais e probabilísticas já utilizadas por Erdős e outros para atacar essas questões e similares.

P. Erdős; R. Faudree; J. Pach; J. Spencer. How to make a graph bipartite
P. Erdős; E. Győri; M. Simonovits. How many edges should be deleted to make a triangle-free graph bipartite?
R. Häggkvist. Odd Cycles of Specified Length in Non-bipartite Graphs

Certos avanços recentes em problemas de grafos livres de triângulos envolvem a técnica de flag algebras, introduzida por Razborov em 2007 e que envolve ideias de álgebra e otimização semidefinida para abordar computacionalmente os problemas que pretendemos estudar.

J. Balogh; F. C. Clemen, B; Lidický. Max Cuts in Triangle-free Graphs
H. Hatami, J. Hladký, D. Král', S. Norine, A. Razborov. On the Number of Pentagons in Triangle-Free Graphs