<p>If you don't care about the constants, then the answer is 'yes' by an easy reduction:</p>

<p>Take a triangle-free graph $G$ with average degree $d_{avg}$. Create a new graph $G'$ which is obtained from $G$ by deleting all vertices with degree $\ge 2d_{avg}$. Obviously, any independent set in $G'$ is an independent set in $G$, and $G'$ is triangle-free. Also, the number of vertices in $G'$ is at least $n(G)/2$. Now we can apply the Alon--Spencer proof.</p>

CC BY-SA 3.0
2014-03-21T15:49:33.597Z
Nice one. This indeed is a very useful trick!
Vivek Bagaria
CC BY-SA 3.0
2014-03-29T11:35:31.823Z
Can we obtain any lower bound on the average degree of the graph G' ?
Vivek Bagaria
CC BY-SA 3.0
2014-03-29T13:03:32.270Z
@Bagaria No. If $G$ was a click of size $n/3$ and an additional $2n/3$ isolated vertices, then $G'$ is just isolated vertices.
greg
CC BY-SA 3.0
2014-03-29T13:36:05.730Z
Any other reduction technique where the max_degree and avg_degree have the same order?
Vivek Bagaria
CC BY-SA 3.0
2014-03-29T16:33:46.670Z
Maybe you can write what the purpose is, rather than properties of the reduction, because when it's not clear what any of this is for, it's hard to give you any useful advice.
greg
CC BY-SA 3.0
2014-03-30T15:17:35.643Z
I am asking the question with respect to the above problem itself. Your reduction technique helps to derive the Bollobas' result from Alon-Spencers's result. But then then bollobass result also ensures that the avg degree of the independent set is a constant times avg degree of the graph, which is not ensures by alon-spencer's proof.
Vivek Bagaria
CC BY-SA 3.0
2014-03-30T23:41:49.910Z
I don't understand what you mean by the word "ensures".
greg
CC BY-SA 3.0
2014-03-31T10:36:54.343Z
By the word "ensure" i meant that the avg degree of the independent set obtained by bollobas' constructive proof is a constant times the avg degree.
Vivek Bagaria
CC BY-SA 3.0
2014-03-21T10:26:02.533Z
2014-03-21T10:26:02.533Z
greg
<p>Consider a triangle-free graph $G$. The notations used are:</p>

<ol>
<li>$\alpha(G) = $ the size of a largest independent set of $G$.</li>
<li>$n(G) = $ the number of vertices in $G$.</li>
</ol>

<p><em>Theorem</em> (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,</p>

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

<p>The book "Probabilistic Methods" by Alon-Spencer gives a very cute proof in the section "The Probabilistic Lens", (pg 272).</p>

<p>But the theorem is true even when $\Delta$ is subsituted by the average degree $d_{avg}$ in the above expression and Bollobas proves this in his book "Random Graphs, 2nd edition", pg 332, using completely different techniques.</p>

<p><strong>My Question :</strong> Can we obtain Bollobas' result by tweaking the technique used by Alon-Spencer?</p>

<p><em>PS:</em> For a graph theory enthusiasts, both proofs are worth reading!</p>

<p>Thanks in advance!</p>

<graph-theory><pr.probability>
Independent set size in triangle-free graphs
Vivek Bagaria
# Independent set size in triangle-free graphs

(Asked by: username_0 on 2014-03-20)

Consider a triangle-free graph $G$. The notations used are:

1. $\alpha(G) = $ the size of a largest independent set of $G$.
2. $n(G) = $ the number of vertices in $G$.

*Theorem* (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,

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

The book "Probabilistic Methods" by Alon-Spencer gives a very cute proof in the section "The Probabilistic Lens", (pg 272).

But the theorem is true even when $\Delta$ is subsituted by the average degree $d\_{avg}$ in the above expression and Bollobas proves this in his book "Random Graphs, 2nd edition", pg 332, using completely different techniques.

**My Question :** Can we obtain Bollobas' result by tweaking the technique used by Alon-Spencer?

*PS:* For a graph theory enthusiasts, both proofs are worth reading!

Thanks in advance!

**Tags:** graph-theory, pr.probability

---

## 1 answers

### Answer by username_1 on 2014-03-21. Score: 4 | Accepted answer

If you don't care about the constants, then the answer is 'yes' by an easy reduction:

Take a triangle-free graph $G$ with average degree $d\_{avg}$. Create a new graph $G'$ which is obtained from $G$ by deleting all vertices with degree $\ge 2d\_{avg}$. Obviously, any independent set in $G'$ is an independent set in $G$, and $G'$ is triangle-free. Also, the number of vertices in $G'$ is at least $n(G)/2$. Now we can apply the Alon--Spencer proof.

> **Comments:**
> **username_0**: Nice one. This indeed is a very useful trick!  
> **username_0**: Can we obtain any lower bound on the average degree of the graph G' ?  
> **username_1**: @Bagaria No. If $G$ was a click of size $n/3$ and an additional $2n/3$ isolated vertices, then $G'$ is just isolated vertices.  
> **username_0**: Any other reduction technique where the max_degree and avg_degree have the same order?  
> **username_1**: Maybe you can write what the purpose is, rather than properties of the reduction, because when it's not clear what any of this is for, it's hard to give you any useful advice.  
> **username_0**: I am asking the question with respect to the above problem itself. Your reduction technique helps to derive the Bollobas' result from Alon-Spencers's result. But then then bollobass result also ensures that the avg degree of the independent set is a constant times avg degree of the graph, which is not ensures by alon-spencer's proof.  
> **username_1**: I don't understand what you mean by the word "ensures".  
> **username_0**: By the word "ensure" i meant that the avg degree of the independent set obtained by bollobas' constructive proof is a constant times the avg degree.  

---

