Números de Ramsey

Introdução e investigação

Resumo

O seguinte trabalho visa elucidar o que está sendo estudado no projeto "Números de Ramsey em grafos multipartidos" e o que se pretende pesquisar ainda. O bolsista realiza os estudos seguindo um cronograma estabelecido pela orientadora e apresenta seminários semanais abertos a quem queira assistir. O tema inicial dos seminários foi a Teoria Clássica dos Grafos, o qual estudamos algumas das definições e dos resultados principais desta teoria, para que então pudéssemos investigar o foco do projeto, que são os Números de Ramsey. Mais formalmente, um grafo é um par de conjuntos G=(V,E), sendo os elementos de V os vértices e os elementos de E as arestas, onde cada aresta é um par não ordenado de vértices distintos. Sobre a Teoria dos Grafos destacamos três conceitos: subgrafo, grafo completo e coloração. Dado um grafo G=(V,E), dizemos queG’=(V’,E’) é um subgrafo de G se V’ é subconjunto de V e E’ de E, grafo completo é um grafo que possui todas as arestas possíveis para o conjunto de vértices, e, coloração de arestas é uma função que associa a cada aresta do grafo uma única cor, por exemplo, uma bicoloração do grafo G=(V,E) é uma função f que associa cada elemento de E a um elemento do conjunto {azul,vermelho}. De posse desses três conceitos podemos introduzir um problema clássico da Teoria de Ramsey: quantas pessoas são necessárias para garantirmos que, três delas se conhecem mutuamente ou três delas se desconhecem? Em 1930, Frank Plumpton Ramsey garantiu que esse número é seis, ou seja, numa festa com seis pessoas sempre existe um grupo de três pessoas que se conhecem mutuamente ou um grupo de três pessoas desconhecidas. A veracidade desta afirmação foi provado por meio da Teoria de Grafos. Podemos modelar esse problema da seguinte forma: considere um grafo completo de nvértices, onde cada vértice representa uma pessoa e cada aresta será colorida de azul se as pessoas representadas pelos vértices que definem esta aresta se conhecem e de vermelho se não se conhecem. Assim, reescrevemos o problema: qual o menor natural n tal que toda bicoloração do grafo completo de n vértices apresenta um triângulo azul ou um triângulo vermelho? Dessa forma, o Número de Ramsey r(s,t) é definido como sendo o menor natural n tal que toda bicoloração do grafo completo com n vértices apresenta um subgrafo completo azul com s vértices ou um subgrafo completo vermelho com t vértices. A partir desse problema surgiram diversos outros e a dificuldade em obter valores exatos de r(s,t) fez essa teoria se expandir, assim apareceram diversos variantes do número de Ramsey, como por exemplo, os número de Ramsey em grafos multipartidos (grafos multipartidos são grafos que possuem o seu conjunto de vértices separado em classes). O estudo desta variante é o principal objetivo deste projeto. Esta pesquisa visa estudar resultados já alcançados, conjecturar novos resultados e provar conjecturas sobre o número de Ramsey em grafos multipartidos.