On $(3,k)$ Ramsey Graphs: Theoretical and Computational Results

Abstract

A $(3,k,n,e)$ Ramsey graph is a triangle-free graph on $n$ vertices with $e$ edges and no independent set of size $k$. Similarly, a $(3,k)$-, $(3,k,n)$-, or $(3,k,n,e)$-graph is a $(3,k,n,e)$ Ramsey graph for some $n$ and $e$. In the first part of the paper, we derive an explicit formula for the minimum number of edges in any $(3,k,n)$-graph for $n\le 3(k-1)$, i.e., a partial formula for the function $e(3,k,n)$ investigated in $[3,5,7]$. We prove some general properties of minimum $(3,k,n)$-graphs with $e(3,k,n)$ edges and present a construction of minimum $(3,k+1,3k-1,5k-5)$-graphs for $k\ge 2$ and minimum $(3,k+1,3k,5k)$-graphs for $k\ge 4$. In the second part of the paper, we describe a catalogue of small Ramsey graphs: all $(3,k)$-graphs for $k\le 6$ and some $(3,7)$-graphs, including all $191(3,7,22)$-graphs, produced by a computer. We present for $k\le 7$ all minimum $(3,k,n)$-graphs and all $10$ maximum $(3,7,22)$-graphs with $66$ edges.