Minimal Ramsey graphs

A Ramsey(s,t;n,e)-graph is a graph with n vertices, e edges, 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 and e. Let e(s,t,n) denote the minimum number of edges in any graph on n vertices without cliques of size s and no independent sets of size t. A Ramsey(s,t;n,e)-graph is minimal if e = e(s,t,n).

Below we list all minimal Ramsey(3,k,n)-graphs for various k and n. See [1] for more information about how these graphs were obtained. Most of these minimal Ramsey graphs are also present in the searchable database and can be found by searching for the keywords 'minimal ramseygraph'.

For a good overview of the results and bounds of Ramsey numbers which are currently known, see Radziszowski's dynamic survey [2].

For a list of all Ramsey(3,≤6)-graphs, see Brendan McKay's page on Ramsey graphs.

The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.

Minimal Ramsey(3,7)-graphs

Vertices No. of graphs
162 (20 edges)
172 (25 edges)
181 (30 edges)
1911 (37 edges)
2015 (44 edges)
214 (51 edges)
221 (60 edges)

Minimal Ramsey(3,8)-graphs

Vertices No. of graphs
192 (25 edges)
203 (30 edges)
211 (35 edges)
2221 (42 edges)
23102 (49 edges)
2451 (56 edges)
25396 (65 edges)
2662 (73 edges)
274 (85 edges)

Minimal Ramsey(3,9)-graphs

Vertices No. of graphs
234 (35 edges)
242 (40 edges)
251 (46 edges)
261 (52 edges)
27700 (61 edges)
28126 (68 edges)
291342 (77 edges)
301800 (86 edges)
31560 (95 edges)
3239 (104 edges)
335 (118 edges)
341 (129 edges)
351 (140 edges)

Minimal Ramsey(3,10)-graphs

Vertices No. of graphs
295 (58 edges)
305084 (66 edges)
312657 (73 edges)
326592 (81 edges)
3357099 (90 edges)

References

[1] J. Goedgebeur and S.P. Radziszowski, New computational upper bounds for Ramsey numbers R(3, k), Electronic Journal of Combinatorics, 20(1), 2013.
[2] S.P. Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey 1, revision 13, 2011.