Versão PDF

A teoria extremal dos grafos é uma área da Combinatória que busca investigar o comportamento de grafos sob certas restrições. Suas aplicações em teoria da computação são vastas, haja visto que um livro inteiro já foi publicado sobre isto [2]. Duas técnicas que têm sido muito bem-sucedidas no estudo de problemas extremais são a teoria de grafos aleatórios e o lema da regularidade de Szemerédi (vide [1] e [3]).

Dado um grafo H, um problema tradicional nessa área consiste em encontrar cotas inferiores para o número de Ramsey R(H), que é definido como o menor número n para o qual existe um grafo G de n vértices tal que qualquer 2-coloração das arestas de G induz uma cópia monocromática do grafo H. Uma variante desse problema consiste em forçar que a cópia induzida de H em G seja isométrica, o que significa que a distância entre os vértices de H é preservada em G. Nesse caso, falamos do número de Ramsey isométrico de H, que aqui denotaremos por RI(H).

Usando a noções de grafos aleatórios e o lema da regularidade de Szemerédi, é possível obter cotas superiores para RI(H). No entanto, os números obtidos através dessas técnicas são muito grandes. Suspeitamos que seja possível obter números melhores aplicando-se o lema da regularidade fraca de Frieze-Kannan, o que tentaremos conseguir nesse trabalho.

Para alcançar esse objetivo, estudaremos as versões de Szemerédi e Frieze-Kannan do lema da regularidade e tópicos na teoria de grafos aleatórios que são necessários para atacar o problema, além de outras aplicações dessas técnicas.

Inicialmente, planejamos a leitura do capítulo 9 de [1] e dos artigos [2] e [3] para uma compreensão mais aprofundada de todas as técnicas mencionadas acima. Em seguida, nos dedicaremos a tentar melhorar o número RI(H) com a regularidade de Frieze-Kannan. Ao final, escreveremos uma apresentação das técnicas estudadas, das suas aplicações em Combinatória e dos resultados obtidos pela nossa pesquisa.

Cronograma

#	Mar	Abr	Mai	Jun	Jul	Ago	Set	Out	Nov
Leitura	x	x	x	x
Tentativa de solução				x	x	x
Escrita da monografia						x	x	x	x

Referências

1. Svante Janson, Tomasz Luczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847
2. Stasys Jukna, Extremal combinatorics, second ed., Texts in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg, 2011, With applications in computer science. MR 2865719
3. J. Koml ́os and M. Simonovits, Szemer ́edi’s regularity lemma and its applications in graph theory, Combinato- rics, Paul Erd ̋os is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud., vol. 2, J ́ anos Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR 1395865
4. Vojtˇech R ̈ odl and Mathias Schacht, Regularity lemmas for graphs, Fete of combinatorics and computer science, Bolyai Soc. Math. Stud., vol. 20, J ́ anos Bolyai Math. Soc., Budapest, 2010, pp. 287–325. MR 2798368

---