<p>Notations</p>

<ol>
<li>$\alpha(G) = $  Max sized independent set of graph $G$.</li>
<li>$n(G) = $ Number of vertex in graph $G$.</li>
</ol>

<p><em>Theorem</em> (by Ajtai et al.): For a <a href="http://en.wikipedia.org/wiki/Triangle-free_graph" rel="nofollow">triangle-free</a> graph $G$ and max degree being $\Delta$,</p>

<p>$$\alpha(G) \geq \frac{n(G)}{8\Delta}\log_2\Delta.$$</p>

<p>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.</p>

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

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

<h2><strong>EDIT 2</strong></h2>

<p>In the <a href="http://arxiv.org/pdf/math.CO/0404325" rel="nofollow">paper</a>, lemma 6 has the following result.</p>

<p><em>Theorem</em> : 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)$$</p>

<p>But I am not able to find the proof for the above theorem.</p>

<p><strong>EDIT3:</strong> Thje proof can be found in "Random Graphs , 2nd edition", pg 332.</p>

CC BY-SA 3.0
2013-10-26T21:17:02.657Z
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
CC BY-SA 3.0
2013-10-28T10:45:51.560Z
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
CC BY-SA 3.0
2013-10-28T13:09:46.163Z
you might have more success with this question on mathoverflow
Sasho Nikolov
CC BY-SA 3.0
2013-10-29T17:49:28.153Z
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
CC BY-SA 3.0
2013-10-30T21:12:04.740Z
Sadly, I am not able to get hold of the first edition of Random Graphs (I have the 2nd edition though)
Vivek Bagaria
CC BY-SA 3.0
2014-03-22T11:06:27.717Z
Are you still interested in this and is it still unsolved? I might be able to come up with a solution if I give it some thought, but I want to check that there's still reason to try.
greg
CC BY-SA 3.0
2014-03-23T15:59:47.870Z
@mobiusdumpling: In my Edit 3, I have given the page number of the book in which the proof is available. Thanks anyways!
Vivek Bagaria
<reference-request><graph-algorithms><approximation-algorithms>
Size of Independent set of sparse graphs with few triangles
Vivek Bagaria
# Size of Independent set of sparse graphs with few triangles

(Asked by: username_0 on 2013-10-26)

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](http://en.wikipedia.org/wiki/Triangle-free_graph) 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](http://arxiv.org/pdf/math.CO/0404325), 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.

**Tags:** reference-request, graph-algorithms, approximation-algorithms
> **Comments:**
> **username_0**: 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.  
> **username_1**: 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).  
> **username_2**: you might have more success with this question on mathoverflow  
> **username_3**: 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?  
> **username_0**: Sadly, I am not able to get hold of the first edition of Random Graphs (I have the 2nd edition though)  
> **username_4**: Are you still interested in this and is it still unsolved? I might be able to come up with a solution if I give it some thought, but I want to check that there's still reason to try.  
> **username_0**: @mobiusdumpling: In my Edit 3, I have given the page number of the book in which the proof is available. Thanks anyways!  

---

## 0 answers

