Análise de um método de coloração no estudo do número de Ramsey R(3,10)
DOI:
https://doi.org/10.35819/remat2022v8i1id4985Palavras-chave:
Teoria de Grafos, Grafos Bicoloridos, Coloração de Grafos, Número de Ramsey, Resíduos de Grau nResumo
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.
Downloads
Referências
ARAÚJO, L. R. Congruências quadráticas, reciprocidade e aplicações em sala de aula. Orientador: Bruno Henrique Carvalho Ribeiro. 2013. 64 f. Dissertação (Mestrado Profissional em Matemática em Rede Nacional) - Universidade Federal da Paraíba, João Pessoa, ago. 2013. Disponível em: https://repositorio.ufpb.br/jspui/bitstream/tede/7480/2/arquivototal.pdf. Acesso em: 28 jan. 2022.
DIESTEL, R. Graph Theory. Eletronic edition 2000. 2. ed. New York: Springer-Verlag, 2000. Disponível em: http://www.esi2.us.es/~mbilbao/pdffiles/DiestelGT.pdf. Acesso em: 28 jan. 2022.
EULER, L. Theoremata circa residua ex divisione potestatum relicta. Novi Commentarii academiae scientiarum Petropolitanae, v. 7, p. 49-82, 1761. Disponível em: https://scholarlycommons.pacific.edu/euler-works/262. Acesso em: 28 jan. 2022.
EXOO, G. On Two Classical Ramsey Numbers of the Form R(3,n). SIAM Journal on Discrete Mathematics, v. 2, n. 4, p. 488-490, 1989. DOI: https://doi.org/10.1137/0402043.
GOEDGEBEUR, J.; RADZISZOWSKI, S. P. New Computational Upper Bounds for Ramsey Numbers R(3,k). Electronic Journal of Combinatorics, v. 20, n. 1, 28 p. 20 mar. 2013. Disponível em: https://arxiv.org/abs/1210.5826. Acesso em: 28 jan. 2022.
GREENWOOD, R. E.; GLEASON, A. M. Combinatorial Relations and Chromatic Graphs. Canadian Journal of Mathematics, v. 7, p. 1-7, 1955. DOI: https://doi.org/10.4153/CJM-1955-001-4.
HARDY, G. H.; WRIGHT, E. M. An Introduction to the Theory of Numbers. 5. ed. Oxford: Oxford University Press, 1979.
RADZISZOWSKI, S. O. Small Ramsey numbers. The Eletronic Journal of Combinatorics. Dynamical survey, revision 16, 15 jan. 2021. Disponível em: https://www.combinatorics.org/files/Surveys/ds1/ds1v16-2021.pdf. Acesso em: 28 jan. 2022.
RAMSEY, F. P. On a Problem of Formal Logic. Proceedings of the London Mathematical Society, v. 2, n. 30, p. 264-286, 13 dez. 1928. DOI: https://doi.org/10.1112/plms/s2-30.1.264.
SANCHES, J. Ferramentas probabilísticas aplicadas a problemas de coloração em grafos. Orientador: Carlos Hoppen.2016. 191 f. Tese (Doutorado em Matemática Aplicada) - Universidade Federal do Rio Grande do Sul, Porto Alegre, dez. 2016. Disponível em: http://hdl.handle.net/10183/153219. Acesso em: 28 jan. 2022.
SANCHES, J. Números de Ramsey em grafos multipartidos. Orientador: Emerson Luiz do Monte Carmelo. 2013. Dissertação (Mestrado em Matemática Aplicada) - Universidade Estadual de Maringá, Maringá, 2013.
SOARES, G. A. M. J. O Teorema de Ramsey e outros resultados de combinatória que não são contagem. Orientador: Carlos Gustavo Moreira. 2014. 45 f. Tese (Mestrado Profissional em Matemática) - Instituto Nacional de Matemática Pura e Aplicada. Rio de Janeiro, 2014. Diponível em: https://impa.br/wp-content/uploads/2016/12/gustavo_adolfo_soares.pdf. Acesso em: 28 jan. 2022.
SPENCER, J. H. Ramsey's Theorem: A New Lower Bound. Journal of Combinatorial Theory, Série A, v. 18, n. 1, p. 108-115, 1975. DOI: https://doi.org/10.1016/0097-3165(75)90071-0.
Downloads
Publicado
Edição
Seção
Licença
Copyright (c) 2022 REMAT: Revista Eletrônica da Matemática
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Os autores detêm os direitos autorais dos artigos publicados e concedem à REMAT o direito de primeira publicação e distribuição de partes ou do trabalho como um todo com o objetivo de promover a revista. Os autores são autorizados a distribuir a versão publicada do artigo, como por exemplo em repositórios institucionais, desde que façam menção de publicação inicial nesta revista a partir da disponibilização do DOI do artigo.
Os artigos são publicados sob a licença Creative Commons Attribution 4.0 International License (CC BY 4.0). Isso permite que o conteúdo seja utilizado para criação de novos trabalhos, tanto para fins comerciais quanto não comerciais, desde que seja feita a devida atribuição ao autor original, conforme especificado na licença.
Como Citar
https://orcid.org/0000-0002-0893-7426
