# Size of Independent set of sparse graphs with few triangles

Notations

1. $\alpha(G) =$ Max sized independent set of graph $G$.
2. $n(G) =$ Number of vertex in graph $G$.

Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8\Delta}\log_2\Delta.$$

For a general graph, $\alpha(G) \geq n(G)/(\Delta+1)$, hence the above result is an improvement by a factor of $\log_2\Delta$. The proof of the above theorem is solely based on the triangle-free property of the graph.

My question: Can one obtain $\alpha(G)$ better than $n(G)/(\Delta+1)$ for graphs with only few triangles?

EDIT 1 - I am looking for solutions where number of triangles, $t=O(n)$.

## EDIT 2

In the paper, lemma 6 has the following result.

Theorem : For a graph $G$ having maximum degree $\Delta$ and having at most T triangles, $$\alpha(G) \geq \frac{n(G)}{10\Delta}\Bigg(\log_2\Delta - \frac{1}{2}\log_2\Big(\frac{T}{n(G)}\Big)\Bigg)$$

But I am not able to find the proof for the above theorem.

EDIT3: Thje proof can be found in "Random Graphs , 2nd edition", pg 332.

• Small (and beautiful) proof for the theorem with triangle-free can be found in appendix A of the book "The Probabilistic Methods" by Noga Alon. – Vivek Bagaria Oct 26 '13 at 21:17
• The very idea of this theorem is because graph is triangle free then many subgraphs are simply have an $\Omega(\Delta)$ independent set, so if you allow to have $O(n)$ triangle you will break this idea, and I doubt that if something similar holds (also I didn't thought about the conterexample, this is just guess). – Saeed Oct 28 '13 at 10:45
• you might have more success with this question on mathoverflow – Sasho Nikolov Oct 28 '13 at 13:09
• The paragraph before the statement of the lemma you quote in Edit 2 cites the proof to page 296 of Bollobas's book Random Graphs (his Lemma 15). Was it not there? – David Richerby Oct 29 '13 at 17:49
• Sadly, I am not able to get hold of the first edition of Random Graphs (I have the 2nd edition though) – Vivek Bagaria Oct 30 '13 at 21:12