Oliver Krüger: On minimal triangle-free Ramsey graphs

Abstract:
A graph G is called a minimal Ramsey (3,k;n)-graph if it has the least amount of edges, e(3,k;n), possible given that G is triangle-free, has independence number α(G) < k and has n vertices. The numbers e(3,k;n) and the minimal Ramsey graphs are directly related to the Ramsey numbers R(3,k).

This licentiate thesis studies minimal Ramsey graphs, graphs that are close to being minimal Ramsey graphs and the edge numbers e(3,k;n) from several different aspects. Lower bounds on e(3,k;n) are lower bounds on the number of edges in triangle-free graphs. In Paper I we show the bound e(G) ≥ (1/3)(17n(G) - 35α(G) - N(C₄;G)), where N(C₄;G) is number of cycles of length four in G. We also classify all triangle-free graphs which satisfy this bound with equality.

In Paper II we study constructions of minimal Ramsey graphs, and graphs G such that e(G)-e(3,k;n) is small. We use a way to describe some of
these graphs in terms of "patterns" and a recursive procedure to construct them. We also present the result of computer calculations where we have actually performed such constructions of Ramsey graphs and compare these lists to other computations of Ramsey graphs.