Ramsey numbers

The Ramsey number R(k,m) is the least integer n such that no matter how we color the edges of the complete graph (clique) with n vertices using two colors red and blue, there is a red clique with k vertices (a red k-clique) or a blue clique with m vertices (a blue m-clique). Ramsey numbers exist for all pairs of positive integers k and m. The problem is to decide whether an integer n satisfies n < R(k,m).

Ramsey number R(4,5). It is known that R(4,5)=25.

INPUT: A set of ground atoms "vtx(i)", i=1,2,...,n, where n is the number of vertices in the clique to be colored.

OUTPUT: a coloring of the edges with red and blue so that neither a red 4-clique nor a blue 5-clique exists. If such a coloring exists, n < R(4,5). Otherwise, R(4,5) <= n.

NOTES:

  1. Suggested values of n for testing:  20, 21, 22 (already quite difficult), 23, and 24 (resolving the case n=24 would be a significant accomplishment for ASP)
Ramsey number R(3,6). It is known that R(3,6)=18.

INPUT: A set of ground atoms "vtx(i)", i=1,2,...,n, where n is the number of vertices in the clique to be colored.

OUTPUT: a coloring of the edges with red and blue so that neither a red 3-clique nor a blue 6-clique exists. If such a coloring exists, n < R(3,6). Otherwise, R(3,6) <= n.

NOTES:

  1. Suggested values of n for testing:  15, 16, 17. Showing there are no solutions for n=18 would be a big accomplishment
Ramsey number R(3,7). It is known that R(3,7)=23.

INPUT: A set of ground atoms "vtx(i)", i=1,2,...,n, where n is the number of vertices in the clique to be colored.

OUTPUT: a coloring of the edges with red and blue so that neither a red 3-clique nor a blue 7-clique exists. If such a coloring exists, n < R(3,7). Otherwise, R(3,7) <= n.

NOTES:

  1. Suggested values of n for testing:  15 and larger. The size of grounding may be prohibitive and poses a real challenge


NOTES:

  1. Another interesting problem is to find lower bounds for the Ramsey number R(3,3,4) - a minimum integer n such that an n-clique, no matter how we color its edges in red, blue and green, has a red 3-clique, a blue 3-clique or a green 4-clique. We will post a detailed description of this problem in the future.