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

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 $α(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})+γ_k]$, where $γ_k=Θ(k^{-6})$.

No reviews yet.

No comments yet.