A lower bound on the hypergraph Ramsey number R(4,5;3)


  • Janusz Dybizbański Institute of Informatics Faculty of Mathematics, Physics, and Informatics University of Gdańsk, 80-308 Gdańsk, Poland




Ramsey numbers


The finite version of Ramsey's theorem says that for positive integers r, k, a_1,... ,a_r, there exists a least number n=R(a_1, \ldots, a_r; k) so that if X is an n-element set and all k-subsets of X are r-coloured, then there exists an i and an a_i-set A so that all k-subsets of A are coloured with the ith colour.

In this paper, the bound R(4, 5; 3) >= 35 is shown by using a SAT solver to construct a red--blue colouring of the triples chosen from a 34-element set.


1. A. Balint and N. Manthey, Sparrow + CP3 and SparrowToRiss, Proc. of SAT Competition 2013: Solver and Benchmark Descriptions (2013), 87-88.

2. B. Bollobas, Modern graph theory, Springer, New York, 1998.

3. P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compos. Math. 2
(1935), 463-470.

4. G. Exoo, Ramsey constructions, http://ginger.indstate.edu/ge/RAMSEY/, Indiana State University.

5. R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, John Wiley & Sons, 1990.

6. H. Harborth and S. Krause, Ramsey numbers for circulant colorings, Congr. Numer. 161 (2003), 139-150.

7. J. R. Isbell, N(4; 4; 3) >= 13, J. Combin. Theory 6 (1969), 210.

8. J. R. Isbell, N(5; 4; 3) >= 24, J. Combin. Theory Ser. A 34 (1983), 379-380.

9. B. D. McKay and S. P. Radziszowski, The first classical Ramsey number for hypergraphs is computed, Proc. of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco), SODA 91, 1991, pp. 304-308.

10. S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin. (2014), Dynamic Survey DS1, revision #14, http://www.combinatorics.org.

11. F. P. Ramsey, On a problem of formal logic, Proc. Lond. Math. Soc. 30 (1930), 264-286.