Recall that a graph is *triangle-free* if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities that tend towards zero as $c \to 0$.

For $c \in [0,1/2]$, let $\mathcal{F}_c$ denote the family of triangle-free graphs $G$ with average degree $d(G) = \Bbb{E}_v[\textrm{deg}(v)] \ge c|V(G)|$. Clearly, for $c>c’$, we have $\mathcal{F}_c\subset \mathcal{F}_{c’}$.

For such $c$, we let $$f(c) = \inf_{G \in \mathcal{F}_c}\{\alpha(G)/|V(G)|\}.$$By our observation above, we have that $f$ is weakly increasing. At the extremes, we have $f(0)=0$ (since there are $n$-vertex triangle-free graphs $G$ with with $\alpha(G) = o(n)$, which trivially have $d(G)\ge 0$), meanwhile $f(1/2)=1/2$ since any triangle-free graph with $d(G)\ge |V(G)|/2$ must be bipartite and hence satisfies $\alpha(G)\ge n/2$.

I am curious about intermediate $c$.

Since neighborhoods are independent sets in triangle-free graphs, our average degree condition implies that $f(c) \ge c$ (since $G\in \mathcal{F}_c \implies c|V(G)| \le d(G) \le \Delta(G) \le \alpha(G)$). However, I don’t know if there exists a matching upper bound.

By the independent work of Bohman-Keevash and Fiz Pontiveros-Griffiths-Morris studying the “triangle-free process”, we get that $f(c) \le (2+o(1))c$. But I don’t know anything stronger.

**Motivation:** I am curious about this quantity because if there existed $\epsilon,c_0> 0$ such that $f(c)>(1+\epsilon)c$ for all $c\in (0,c_0)$, this would imply a significantly better upper bound for $R_k(3)$ (the $k$-color Ramsey number of $K_3$).

**What I'm looking for:**

Ultimately, I hope to learn that one of the following possibilities is true:

- This is a known open problem.
- We have that $f(c) = (1+o(1))c$ (or, some partial result like $f(c)<(2-\epsilon)c$ for small $c$).
- We have that $f(c) > (1+\epsilon)c$ for all small $c$.

If case 3 is true, then someone should write a paper about this, since it gives the first improvement to the upper bound of $R_k(3)$ in over 100 years (besides slight improvements to the implicit constant)!

It is also possible that this is a very hard problem, which hasn't been stated in literature. In which case, there might not be a satisfying conclusion to my question.