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

Autores

  • Danielle Santos Azevedo Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil https://orcid.org/0000-0003-2008-6086
  • Jonas Francisco de Medeiros Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil https://orcid.org/0000-0002-3662-5243
  • Daniel Coswig Zitzke Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil https://orcid.org/0000-0001-5292-4051
  • Rafael Rodrigues Pereira Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil https://orcid.org/0000-0002-7005-4755
  • Lenon Saturnino Bernardino Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil https://orcid.org/0000-0002-6064-0929

DOI:

https://doi.org/10.35819/remat2022v8i1id4985

Palavras-chave:

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

Resumo

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

Não há dados estatísticos.

Biografia do Autor

Danielle Santos Azevedo, Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil

Jonas Francisco de Medeiros, Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil

Daniel Coswig Zitzke, Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil

Rafael Rodrigues Pereira, Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil

Lenon Saturnino Bernardino, Instituto Federal de Educação, Ciência e Tecnologia do Rio Grande do Sul (IFRS), Campus Alvorada, Alvorada, RS, Brasil

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

2022-01-31

Como Citar

AZEVEDO, D. S.; MEDEIROS, J. F. de; ZITZKE, D. C.; PEREIRA, R. R.; BERNARDINO, L. S. Análise de um método de coloração no estudo do número de Ramsey R(3,10). REMAT: Revista Eletrônica da Matemática, Bento Gonçalves, RS, v. 8, n. 1, p. e3001, 2022. DOI: 10.35819/remat2022v8i1id4985. Disponível em: https://periodicos.ifrs.edu.br/index.php/REMAT/article/view/4985. Acesso em: 27 maio. 2022.

Edição

Seção

Matemática