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.
REMAT conserva los derechos de autor de los artículos publicados, teniendo derecho a la primera publicación del trabajo, mención de la primera publicación en la revista en otros medios publicados y distribución de partes o del trabajo en su conjunto con el fin de promover la revista.
Esta es una revista de acceso abierto, lo que significa que todo el contenido está disponible de forma gratuita, sin costo para el usuario o su institución. Los usuarios pueden leer, descargar, copiar, distribuir, imprimir, buscar o vincular los textos completos de los artículos, o utilizarlos para cualquier otro propósito legal, sin solicitar permiso previo a la revista o al autor. Esta declaración está de acuerdo con la definición de BOAI de acceso abierto.
Cómo citar
https://orcid.org/0000-0002-0893-7426
