The next case of Andrásfai's conjecture

Abstract

Let $\mathrm{ex}(n,s)$ denote the maximum number of edges in a triangle-free graph on $n$ vertices which contains no independent sets larger than $s$. The behaviour of $\mathrm{ex}(n,s)$ was first studied by Andrásfai, who conjectured that for $s>n/3$ this function is determined by appropriately chosen blow-ups of so called Andrásfai graphs. Moreover, he proved $\mathrm{ex}(n,s)=n^2-4ns+5s^2$ for $s/n\in [2/5,1/2]$ and in earlier work we obtained $\mathrm{ex}(n,s)=3n^2-15ns+20s^2$ for $s/n\in [3/8,2/5]$. Here we make the next step in the quest to settle Andrásfai's conjecture by proving $\mathrm{ex}(n,s)=6n^2-32ns+44s^2$ for $s/n\in [4/11,3/8]$.

Dedicated to the memory of Vera T. Sós. Second version addresses comments from referee reports