Análisis de un método de coloración en el estudio del número de Ramsey R (3,10)
DOI:
https://doi.org/10.35819/remat2022v8i1id4985Palabras clave:
Teoría de Grafos, Gráficos Bicolores, Coloración Gráfica, El Número de Ramsey, Residuales de Grado nResumen
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 [...].
Descargas
Referencias
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.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2022 REMAT: Revista Eletrônica da Matemática
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
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.
Última atualização: 07/02/2025, 19:22.
Cómo citar
