Andrásfai and Vega graphs in Ramsey-Turán theory

Abstract

Given positive integers $n\ge s$, we let $\mathrm{ex}(n,s)$ denote the maximum number of edges in a triangle-free graph $G$ on $n$ vertices with $\alpha (G)\le s$. In the early sixties Andrásfai conjectured that for $n/3<s<n/2$ the function $\mathrm{ex}(n,s)$ is piecewise quadratic with critical values at $s/n=k/(3k-1)$. We confirm that this is indeed the case whenever $s/n$ is slightly larger than a critical value, thus determining $\mathrm{ex}(n,s)$ for all $n$ and $s$ such that $s/n\in [k/(3k-1),k/(3k-1)+{\gamma }_k]$, where ${\gamma }_k=\Theta (k^{-6})$.

Revised according to referee reports