# Dense triangle-free graphs and their independent sets

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.

• $\alpha(G)=$ independence number (size of largest independent set) is standard notation but maybe worth saying explicitly somewhere in the post... Aug 6, 2022 at 21:55
• Interesting that you choose to explain the self-explanatory term "triangle-free" but leave us to guess at the meaning of $\alpha(G)$ which in some books is the independence number and in others is the vertex covering number.
– bof
Aug 7, 2022 at 6:13
• I guess it was because I see $\alpha(G)$ appear in papers much more often (and never see the vertex cover thing). edited. Aug 7, 2022 at 6:58

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).