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.

  • 1
    $\begingroup$ $\alpha(G)=$ independence number (size of largest independent set) is standard notation but maybe worth saying explicitly somewhere in the post... $\endgroup$ Aug 6, 2022 at 21:55
  • $\begingroup$ 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. $\endgroup$
    – bof
    Aug 7, 2022 at 6:13
  • $\begingroup$ I guess it was because I see $\alpha(G)$ appear in papers much more often (and never see the vertex cover thing). edited. $\endgroup$ Aug 7, 2022 at 6:58

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


Your Answer

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

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