On the Ramsey-Turán density of triangles

Abstract

One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graphs on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges. About half a century later Andrásfai studied dense triangle-free graphs and proved that the largest triangle-free graphs on $n$ vertices without independent sets of size $\alpha n$, where $2/5\le \alpha <1/2$, are blow-ups of the pentagon. More than 50 further years have elapsed since Andrásfai's work. In this article we make the next step towards understanding the structure of dense triangle-free graphs without large independent sets. Notably, we determine the maximum size of triangle-free graphs~$G$ on $n$ vertices with $\alpha (G)\ge 3n/8$ and state a conjecture on the structure of the densest triangle-free graphs $G$ with $\alpha (G)>n/3$. We remark that the case $\alpha (G)\le n/3$ behaves differently, but due to the work of Brandt this situation is fairly well understood.

arXiv commentRevised according to referee reports

References in corpus (2)

• The Ramsey-Turán problem for cliques
• Andrásfai and Vega graphs in Ramsey-Turán theory

Cited by in corpus (1)

• K_4-free graphs have sparse halves