# Sizes of triangle-free graphs with independence number $k$

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?

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?