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!


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.

| cite | improve this answer | |
  • $\begingroup$ Nice one. This indeed is a very useful trick! $\endgroup$ – Vivek Bagaria Mar 21 '14 at 15:49
  • $\begingroup$ Can we obtain any lower bound on the average degree of the graph G' ? $\endgroup$ – Vivek Bagaria Mar 29 '14 at 11:35
  • $\begingroup$ @Bagaria No. If $G$ was a click of size $n/3$ and an additional $2n/3$ isolated vertices, then $G'$ is just isolated vertices. $\endgroup$ – mobius dumpling Mar 29 '14 at 13:03
  • $\begingroup$ Any other reduction technique where the max_degree and avg_degree have the same order? $\endgroup$ – Vivek Bagaria Mar 29 '14 at 13:36
  • $\begingroup$ 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. $\endgroup$ – mobius dumpling Mar 29 '14 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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