Estudio del número de Ramsey R(3,10): análisis de gráficas de orden 40
DOI:
https://doi.org/10.35819/remat2023v9i2id6424Palabras clave:
teoría de grafos, grafos bicolores, números de Ramsey, clic, conjunto independienteResumen
El número de Ramsey R(k,l) es el entero más pequeño n tal que no hay (k,l,n,e)-grafo, donde un (k,l,n,e)-grafo denota un grafo G con n vértices y e aristas y con C(G)<k e I(G)<l, en que C(G) denota el clic más grande en G y I(G) denota el conjunto independiente más grande en G. La teoría de grafos dio origen a una extensa investigación, pues por más simple que sea la definición, calcular los números de Ramsey es una tarea ardua y que pocos conocen. Exoo (1989), Goedgebeur y Radziszowski (2013) mostraron que 40 <= R(3,10) <= 42. Así, en este artículo expondremos proposiciones que serán de utilidad en el cálculo de este número de Ramsey. Basado en las ideas de Grinstead y Roberts (1982) y Cariolaro (2007), se mostrarán las propriedades e caracteristicas para un grafo G bicolor de orden 40, tal que G está libre de triángulos, esto es, C(G)<3, y no tiene un conjunto independiente de orden 10, es decir, I(G)<10. Mostraremos, por ejemplo, que dado G = (V,E) un grafo de orden 40 y con C(G) < 3 y I(G) < 10, entonces, para todo vértice v en V, tenemos que 4 <= deg(v) <= 9. Finalmente, destacamos que los resultados inéditos obtenidos por los autores, en un proyecto de investigación desarrollado en IFRS, Campus Alvorada, se encuentran en la Sección 4.
Descargas
Referencias
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: https://doi.org/10.35819/remat2022v8i1id4985.
CARIOLARO, D. On the Ramsey number R(3,6). Australasian Journal of Combinactorics, v. 37, p. 301-304, 2007. Disponível em: https://ajc.maths.uq.edu.au/pdf/37/ajc_v37_p301.pdf. Acesso em: 17 out. 2023.
DIESTEL, R. Graph Theory. 2. ed. eletronic edition. New York: Springer-Verlag, 2000.
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 Combinactorics, v. 20, n. 1, 2013. DOI: https://doi.org/10.37236/2824.
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.
GRINSTEAD, C. M.; ROBERTS, S. M. On the Ramsey numbers R(3,8) and R(3,9). Journal of Combinatorial Theory, v. 33, p. 27-51, 1982.
Radziszowski, S. Small Ramsey Numbers. The Electronic Journal of Combinatorics. 1994. Revisão de 2021. DOI: https://doi.org/10.37236/21.
RAMSEY, F. P. On a Problem of Formal Logic. Proceedings of the London Mathematical Society, v. 2, n. 30, p. 264-286, 1930. 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. 151 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: 19 out. 2023.
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.
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 2023 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
