Dense triangle-free graphs and their independent sets

Question

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.

Answer 1

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 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 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 verified this for a small portion of $c$'s, even giving the precise form of $f(c)$ (it is conjectured to be piecewise quadratic).