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)

All maximal Ramsey(4,5)-graphs

In 1995, McKay and Radziszowski proved that there are no Ramsey(4,5)-graphs with more than 24 vertices and found 350904 of them with 24 vertices. The remainder were found in 2016 by McKay and Angeltveit. There are 352366 altogether, see r45_24.g6.

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-47 vertices. r55_42some.g6 contains 328 of these graphs; the other 328 are their complements.

The Ramsey(4,4;3)-hypergraphs

A Ramsey(4,4;3)-hypergraph is a 3-uniform hypergraph with this property: every set of 4 vertices contains 1, 2 or 3 edges (not 0 or 4). The smallest number of vertices on which no such hypergraph exists is called the hypergraph Ramsey number R(4,4;3). In 1991, McKay and Radziszowski proved that R(4,4;3)=13. The full set of Ramsey(4,4;3)-hypergraphs with 12 vertices was found by McKay in 2016. Note that the complement of a Ramsey(4,4;3)-hypergraph is also a Ramsey(4,4;3)-hypergraph, so in the following files we omit hypergraphs having more edges than their complements.

Each hypergraph occupies one text line. First there are the number of vertices and the number of edges, then there is a list of edges using letters abc.. as vertex names. There are almost 1012 Ramsey(4,4;3)-hypergraphs altogether, so for some sizes we will just give those with few edges.

4 vertices (1 hypergraph)
5 vertices (4 hypergraphs)
6 vertices (78 hypergraphs)
7 vertices (7213 hypergraphs)
8 vertices (gzipped) (5835963 hypergraphs)
9 vertices (gzipped) (796865 hypergraphs with at most 36 edges)
10 vertices (123179 hypergraphs with at most 52 edges)
11 vertices (251060 hypergraphs with at most 75 edges)
12 vertices (gzipped) (282713 hypergraphs)

Ramsey tournaments

Here are the largest touraments which contain no transitive subtournament of order k, for small k. For 3≤k≤6, the maximum tournament is unique. For k=7, the order isn't even known; it could be anything from 33 to 46. Neiman, Mackey and Heule found 49 examples with 33 vertices. We have expanded that to 5305 tournaments, but there may be more. Unfortunately, none of them extend to 34 vertices.

k=3 (3 vertices, unique)
k=4 (7 vertices, unique)
k=5 (13 vertices, unique)
k=6 (27 vertices, unique)
k=7 (33 vertices, 5305 tournaments)

 


Page Master: Brendan McKay, brendan.mckay@anu.edu.au and https://users.cecs.anu.edu.au/~bdm.

Up to the combinatorial data page