ramsey numbers

An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs

Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming Tags , , , ,

The Ramsey number R(m,n) is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size m or a red clique of size n. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that … Read more

A New Bilevel Optimization Approach for Computing Ramsey Numbers

Categories 0-1 Programming, Graphs and Matroids, Network Optimization Tags , , , ,

In this article we address the problem of finding lower bounds for small Ramsey numbers $R(m,n)$ using circulant graphs. Our constructive approach is based on finding feasible colorings of circulant graphs using Integer Programming (IP) techniques. First we show how to model the problem as a Stackelberg game and, using the tools of bilevel optimization, … Read more