O desafio dos números de Ramsey: explorando a eficiência de algoritmos aleatórios e genéticos na busca por contraexemplos

Abstract

This work addresses fundamental concepts of Graph Theory, including complete graphs, empty graphs, and the concept of graph complement. It reviews essential concepts, such as the degree of a vertex, neighborhood, and highlights the importance of Turán’s Theorem in defining edge bounds to avoid complete subgraphs. It details the original Ramsey problem and the modern formulation. It highlights the difficulty of finding exact Ramsey numbers and the contribution of Paul Erd˝os to the theory. The main objective of this study is to explore the application of heuristics, specifically genetic and random algorithms, to find counterexamples to the Ramsey problem. The study seeks to analyze how these approaches can be used to solve complex problems in Graph Theory, focusing on the determination of graphs that satisfy certain Ramsey properties. It concludes that the use of genetic algorithms is a viable approach to find counterexamples to the Ramsey problem, despite the associated limitations and computational challenges.