Oliver Krüger: The minimum edge numbers of triangle-free graphs and some related invariants

Abstract

The minimum edge numbers, e(3,k,n), are defined as the least number of edges in
a triangle free graph on n vertices without an independent set of size k. These
numbers are sometimes useful in determining and bounding the classical
two-colour Ramsey numbers R(3,l) for low values of l.

Radziszowski and Kreher determined lower bounds for e(3,k+1,n) by studying
linear graph invariants such as e(G) - 6n(G) + 13α(G) and establishing that this
is non-negative for all triangle-free graphs G. In this talk, I will present
a recent result in a similar vain, establishing the non-negativity of the
invariant ν(G) := 3e(G) - 17n(G) + 35α(G) + N(C₄;G), where N(C₄;G) denotes the
number of cycles of length four in G.

In this talk I will discuss these results and their connection to two-colour
Ramsey theory for graphs. I will also try to motivate the invariant ν(