4
$\begingroup$

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?

$\endgroup$

1 Answer 1

6
$\begingroup$

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:

andrasfai graph

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.