The Ramsey coloring problem is described here:
https://charlesgretton.github.io/2024symposium/optimal.html#/6
For small cliques solutions can be found using a Boolean SAT procedure. For larger cliques, the problem becomes too challenging for known SAT procedures.
Transformers offer a compelling heuristic approach to scale search to larger cliques. Combining search with transformers, one might hope to push the envolope on the scale of problem we can solve. Existing related work using transformers is published here:
https://arxiv.org/pdf/2411.00566
This project is appropriate for an 24 unit honours thesis.
Students who wish to do this project should apply for an honours grant, here:
https://study.anu.edu.au/scholarships/find-scholarship/co-lab-honours-grant