Ramsey Graphs

Here we present some graphs related to classical Ramsey numbers. A Ramsey(s,t,n)-graph is a graph with n vertices, no clique of size s, and no independent set of size t. A Ramsey(s,t)-graph is a Ramsey(s,t,n)-graph for some n. Ramsey Theory tells us that there are only a finite number of Ramsey(s,t)-graphs for each s and t, but finding all such graphs, or even determining the largest n for which they exist, is a famously difficult problem.

For a survey of the latest results on Ramsey graphs, see Radziszowski's Dynamic Survey at the Electronic Journal of Combinatorics. For information on the data format used below, see the combinatorial data page.

All Ramsey(3,4)-graphs

1 vertex (1 graph)
2 vertices (2 graphs)
3 vertices (3 graphs)
4 vertices (6 graphs)
5 vertices (9 graphs)
6 vertices (15 graphs)
7 vertices (9 graphs)
8 vertices (3 graphs)

All Ramsey(3,5)-graphs

1 vertex (1 graph)
2 vertices (2 graphs)
3 vertices (3 graphs)
4 vertices (7 graphs)
5 vertices (13 graphs)
6 vertices (32 graphs)
7 vertices (71 graphs)
8 vertices (179 graphs)
9 vertices (290 graphs)
10 vertices (313 graphs)
11 vertices (105 graphs)
12 vertices (12 graphs)
13 vertices (1 graph)

All Ramsey(3,6)-graphs

1 vertex (1 graph)
2 vertices (2 graphs)
3 vertices (3 graphs)
4 vertices (7 graphs)
5 vertices (14 graphs)
6 vertices (37 graphs)
7 vertices (100 graphs)
8 vertices (356 graphs)
9 vertices (1407 graphs)
10 vertices (6657 graphs)
11 vertices (gzipped) (30395 graphs)
12 vertices (gzipped) (116792 graphs)
13 vertices (gzipped) (275086 graphs)
14 vertices (gzipped) (263520 graphs)
15 vertices (gzipped) (64732 graphs)
16 vertices (gzipped) (2576 graphs)
17 vertices (7 graphs)

All maximal Ramsey(3,7)-graphs

21 vertices (gzipped) (1118436 graphs; found by Gunnar Brinkmann and Jan Goedgebeur)
22 vertices (191 graphs)

All maximal Ramsey(3,8)-graphs

McKay and Zhang proved that the largest Ramsey(3,8)-graphs have 27 vertices in 1992, but the full set of Ramsey(3,8,27)-graphs was not determined until Gunnar Brinkmann and Jan Goedgebeur did it in 2012.

27 vertices (gzipped) (477142 graphs)

All maximal Ramsey(3,9)-graphs

The maximal Ramsey(3,9)-graph has 35 vertices and was found by Kalbfleisch long ago, but it took until 2013 for its uniqueness to be proved. See the paper of Goedgebeur and Radziszowski.
35 vertices (1 graph)

All Ramsey(4,4)-graphs

1 vertex (1 graph)
2 vertices (2 graphs)
3 vertices (4 graphs)
4 vertices (9 graphs)
5 vertices (24 graphs)
6 vertices (84 graphs)
7 vertices (362 graphs)
8 vertices (2079 graphs)
9 vertices (14701 graphs)
10 vertices (gzipped) (103706 graphs)
11 vertices (gzipped) (546356 graphs)
12 vertices (gzipped) (1449166 graphs)
13 vertices (gzipped) (1184231 graphs)
14 vertices (gzipped) (130816 graphs)
15 vertices (640 graphs)
16 vertices (2 graphs)
17 vertices (1 graph)

Some maximal Ramsey(4,5)-graphs

McKay and Radziszowski proved that there are no Ramsey(4,5)-graphs with more than 24 vertices. The full set of Ramsey(4,5,24)-graphs has not been determined, but r45_24some.g6.gz contains the 350904 that are known.

The largest known Ramsey(4,6)-graphs

In early 2012, Geoffrey Exoo raised the lower bound on R(4,6) by discovering 37 Ramsey(4,6,35)-graphs. There could be more, and there might even be some with 36-40 vertices. See r46_35some.g6.

The largest known Ramsey(5,5)-graphs

Geoffrey Exoo found several Ramsey(5,5,42)-graphs in 1989. McKay and Radziszowski expanded this to 656 graphs and conjectured that there are none larger. However, there could be more with 42 vertices and even some with 43-48 vertices. r55_42some.g6 contains 328 of these graphs; the other 328 are their complements.

 


Page Master: Brendan McKay, bdm@cs.anu.edu.au and http://cs.anu.edu.au/~bdm.

Up to the combinatorial data page