Análise de um método de coloração no estudo do número de Ramsey R(3,10)

Abstract

Sejam s, t números naturais; o número de Ramsey R(s,t) é o menor inteiro positivo r tal que para toda bicoloração de Kr, digamos azul e vermelho, existe um subgrafo Ks monocromático de cor azul ou um subgrafo monocromático Kt vermelho. Essa teoria deu origem a vastas pesquisas utilizando, entre outros assuntos, o estudo de combinatória, iniciado com Ramsey (1928). Por mais simples que seja a definição, calcular os números de Ramsey é muito difícil e poucos são conhecidos. Exoo (1989), e Goedgebeur e Radziszowski (2013) mostraram que 40 <= R(3,10) <= 42. Assim, neste artigo, serão exibidos estudos e conclusões sobre uma bicoloração para R(3,10). Ainda não podemos afirmar que os resultados apresentados neste trabalho serão usados no cálculo final do número de Ramsey R(3,10). A ideia, aqui, é compartilhar o que estudamos em nosso grupo de pesquisa, a fim de que esses estudos sejam usados no cálculo de R(3,10) ou para mostrar aos colegas que também estudam números de Ramsey, o que já fizemos, evitando, assim, um retrabalho. Greenwood e Gleason (1955) usaram as noções de resíduos cúbicos e quadráticos, respectivamente, para mostrar que R(3,5)=14 e R(4,4)=17. Baseado nessas ideias, dado um grafo completo com 41 vértices, de forma isomorfa, vamos identificar esses vértices com os elementos {0, ..., 40} de um corpo com 41 elementos. E, com uma bicoloração usando resíduos de grau n módulo m (m, n naturais), vamos mostrar que esse grafo contém uma cópia de K3 azul ou uma cópia de K10 vermelha.

Keywords

• Teoria de Grafos
• Grafos Bicoloridos
• Coloração de Grafos
• Número de Ramsey
• Resíduos de Grau n