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.
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)
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)
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)
21 vertices (gzipped) (1118436 graphs; found by Gunnar Brinkmann and Jan Goedgebeur)
22 vertices (191 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)
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)
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)
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.
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.
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.
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
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)
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.