A triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. The independence number $α = α(G)$ of a graph $G$ is the cardinality of a maximum in dependent set of vertices.
The following theorem is well-known.
Mantel’s theorem. Let $G$ be a triangle-free graph with $n$ vertices. Then $G$ contains at most $\lfloor \frac{n^2}{4} \rfloor$ edges. Furthermore, the only triangle-free graph with $\lfloor \frac{n^2}{4} \rfloor$ edges is the complete graph $K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil }$.
We observe that the unique extremal graph ($K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil }$) has independence number $α =\lceil \frac{n}{2} \rceil $. Therefore, I would like to inquire if the following question has been investigated.
Problem. Let $G$ be a triangle-free graph with $n$ vertices and $α(G) = k $ where $k\ne \lceil \frac{n}{2} \rceil $. Then what is the upper bound on the number of edges in $G$?
For small values of $k$, such as $k= 3, 4, 5$, is there an exact solution to this problem?
Has this problem been studied before?
Best Answer
The problem is called the Ramsey-Turán density on triangles if $k$ is understood to be $\Theta(n)$.
Let $\text{ex}(n, \alpha n)$ be the maximum number of edges of a $n$-vertex triangle-free graph $G$ with independence number at most $\alpha n$, and let $f(\alpha)$ be $\underset{n \rightarrow \infty} \lim \frac{\text{ex}(n, \alpha n)} {n(n-1)/2}$.
Since the neighbourhood of any vertex of $G$ is an independent set, $f(\alpha) \leq \alpha$.
When $\alpha \leq 1/3$, Brandt constructed graphs with $f(\alpha)=\alpha$ in the paper Triangle-free graphs whose independence number equals the degree.
When $\alpha \gt 1/3$, the conjecture is that $f(\alpha)$ is piecewise quadratic with critical values corresponding to (blowups of) Andrásfai graphs:
The conjecture is stated and known for $3/8 \leq \alpha \leq 1/2$, corresponding to Andrásfai graphs for $n=1,2,3$.
For small values of $k$, I have used SageMath (i.e. nauty_geng graph generation) and Ramsey number bounds to check that:
for $k=3$, $G$ can have at most $12$ edges, and the only graph attaining this is the Wagner graph.
for $k=4$, $G$ can have at most $26$ edges, and the only graph attaining this is the 13-cyclotomic graph.
for $k=5$, $G$ can have at most $42$ edges, with the following graph6 strings:
P?AA@AOy@TM_m_apAyAZ?TQ?
P?AA@AOy@TM_ZGTQ@[cu?Ds?