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

Ano: 2022 | Volume: 8 | Número: 1

Autores: Danielle Santos Azevedo, Jonas Francisco de Medeiros, Daniel Coswig Zitzke, Rafael Rodrigues Pereira, Lenon Saturnino Bernardino

Palavras-chave: Teoria de Grafos; Grafos Bicoloridos; Coloração de Grafos; Número de Ramsey; Resíduos de Grau n

Resumo Português:

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.

Resumo Inglês:

Let s, t natural numbers; the Ramsey number R(s,t) is defined as the least positive integer $r$ with the property that every bicolored graph Kr contains one blue monocramatic subgraph Ks or one red monocramatic subgraph Kr. This theory gave rise to extensive research using, among other subjects, the study of combinatorics, started with Ramsey (1928). As simple as the definition is, calculating Ramsey numbers is very difficult and few are known. Exoo (1989), and Goedgebeur and Radziszowski (2013) showed that 40 <= R(3,10) <= 42. Thus, in this article, will be displayed studies and conclusions about R(3,10). We cannot yet state that the results presented in this article will be used in the final calculation of the Ramsey number R(3,10). The idea here is to share what we have studied in our research group, so that these studies can be used in the calculation of R(3,10) or to show colleagues who also study Ramsey numbers, which already we did, thus avoiding rework. Greenwood and Gleason (1955) used the notions of cubic and quadratic residues, respectively, to show that R(3,5)=14 and R(4,4)=17. Based on these ideas, given a complete graph with 41 vertices, in an isomorphic form, we will identify these vertices with the elements {0, ..., 40} of a field with 41 elements. And, with a bicoloration using residues of degree n module m (natural m, n), we will show that this graph contains a copy of blue K3 or a red copy of K10.

Resumo Espanhol:

Sean s, t números naturales; el número de Ramsey R(s,t) es el entero positivo más pequeño r tal que para cada bicolor de Kr, digamos azul y rojo, hay un subgrafo Ks color azul monocromático o un subgrafo monocromático rojo Kt. Esta teoría dio lugar a vastas investigaciones que utilizaron, entre otros temas, el estudio de la combinatoria, iniciado con Ramsey (1928). Tan simple como es la definición, calcular los números de Ramsey es muy difícil y se conocen pocos. Exoo (1989), y Goedgebeur y Radziszowski (2013) mostraron que 40 <= R (3,10) <= 42. Así, en este artículo se mostrarán estudios y conclusiones sobre un bicolor por R(3,10). Todavía no podemos decir que los resultados presentados en este trabajo se utilizarán en el cálculo final del número de Ramsey R(3,10). La idea aquí es compartir lo que hemos estudiado en nuestro grupo de investigación, para que estos estudios puedan usarse en el cálculo de R(3,10) o para mostrar a colegas que también estudian números de Ramsey, lo cual ya hicimos, así evitando un trabajo. Greenwood y Gleason (1955) utilizaron las nociones de residuos cúbicos y cuadráticos, respectivamente, para mostrar que R (3,5)=14 y R(4,4)=17. En base a estas ideas, dado un gráfico completo con 41 vértices, en forma isomorfa, identificaremos estos vértices con los elementos {0, ..., 40} de un campo con 41 elementos. Y, con un bicolor usando residuos de grado n módulo m (m, n naturales), demostremos que este gráfico contiene una copia azul de K3 o una copia de K10 rojo.