Hybrid reinforcement learning and classical graph checking approach for restricted and connected size Ramsey numbers of 3K2 and cycles

Given simple graphs F, G, and H, we say that F → (G, H) if, for any red-blue coloring of the edges of F, there exists either a red-colored copy of G or a blue-colored copy of H. The Ramsey number r(G, H) is the smallest integer r such that the complete graph K r satisfies K r → (G, H). The size Ramsey number rˆ(G, H) is the smallest number of edges in a graph F that satisfies F → (G, H). In addition, we distinguish two key variations of size Ramsey numbers: the restricted size Ramsey number and the connected size Ramsey number. The restricted version limits the graph F to a certain class of graphs, while the connected variant requires that the Ramsey configuration must appear in a connected subgraph of F. In this paper, we investigate algorithmic techniques for computing the restricted and connected size Ramsey numbers for 3K 2 versus cycles. The problem of determining the values of such numbers is an open and challenging problem, with very little known in this area. The developed algorithms must utilize a variety of graph properties. We introduce an approach that combines a reinforcement learning-based local search (RLS) method with a verification procedure using Nauty. Our results provide new exact values for both the restricted and connected cases. These findings represent an initial step in exploring this topic, laying the groundwork for further research.