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:


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



Dense triangle-free graphs and their independent sets
The answer turns out to be a mix of options 2 and 3. As you have noticed, we always have that $\alpha(G)\geq d(G)$. We could ask for what values of $c$ could the equality hold, i.e. for any vertex $v$ in $G$, its neighbors always form a maximum independent set.


[Sidorenko](https://www.sciencedirect.com/science/article/pii/0012365X9190114H/pdf?md5=d9891f1dea85f89cf3cdd374c560fbad&pid=1-s2.0-0012365X9190114H-main.pdf) showed that the Cayley graphs on $\mathbb{Z}\_n$ with the generators $\{\pm k,\ldots, \pm(2k-1)\}$ are such triangle-free graphs whenever $6k-2\leq n\leq 8k-3$. This basically shows that $f(c)=c$ for any $c\in [1/4, 1/3]$.


To extend this to sparser graphs, [Brandt](https://www.sciencedirect.com/science/article/pii/S0012365X09002817#b21) used a well-known construction of Mycielski to iteratively grow the graph up (and thus reduce the density of the graph) while maintaining the properties we want. This itself already shows that $f(c)=c$ for any $c\leq 1/3$. In the paper, some extra steps were done so that for every sufficiently small $c$, there is a corresponding graph that matches $c$ exactly.


In the same paper, Brandt also pointed out that if the density of such graph lies strictly between $1/3$ and $1/2$, then it must be of the form $i/(3i-1)$ for some positive integer $i$. Therefore one would expect that $f(c)$ is slightly larger than $c$ in this interval outside those critical points.
[Łuczak, Polcyn and Reiher](https://arxiv.org/abs/2002.01498) verified this for a small portion of $c$'s, even giving the precise form of $f(c)$ (it is conjectured to be piecewise quadratic).


