INTRODUÇÃO À TEORIA DE RAMSEY PARA GRAFO

Abstract

Neste trabalho foram estudados os fundamentos da Teoria de Ramsey aplicada à Teoria de Grafos. Grafos são estruturas combinatórias formadas por um conjunto de pontos (chamados vértices) e um conjunto de pares desses pontos (chamados arestas). Os grafos possuem grande importância devido à sua enorme versatilidade, podendo ser aplicados a diversas áreas, como Ciência da Computação, Biologia, Física e Química. A Teoria de Ramsey, por sua vez, teve seus primeiros resultados em lógica formal por volta de 1927, mas, com o passar do tempo, começou a ser estudada para várias outras estruturas, sendo que Ramsey para Grafos é uma das suas formas mais intuitivas e naturais. O Teorema de Ramsey pode ser interpretado como uma forte generalização do Princípio da Casa dos Pombos, garantindo a existência de uma dada estrutura monocromática dentro de uma estrutura suficientemente grande multi-colorida. No caso de grafo, a estrutura desejada é um grafo completo monocromático, ou seja, em que todo par de vértices é uma aresta e todas as arestas possuem a mesma cor; e a estrutura grande é um grafo completo cujas arestas são coloridas de forma arbitrária com um número pré-fixado de cores. A fim de introduzir esse tema, serão apresentadas algumas definições básicas relacionadas a grafos e colorações, será definido o Número de Ramsey de um grafo e serão apresentados limitantes simples para o Número de Ramsey de grafos completos. Também será evidenciado um resultado mais recente que trata do Número de Ramsey para caminhos,demonstrada a parti de uma conjectura de Allen,Brightwell e Skokan . Agradece-se ao CNPq pelo apoio financeiro.