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


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.

  • $\begingroup$ 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. $\endgroup$ – Vivek Bagaria Oct 26 '13 at 21:17
  • $\begingroup$ 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). $\endgroup$ – Saeed Oct 28 '13 at 10:45
  • $\begingroup$ you might have more success with this question on mathoverflow $\endgroup$ – Sasho Nikolov Oct 28 '13 at 13:09
  • $\begingroup$ 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? $\endgroup$ – David Richerby Oct 29 '13 at 17:49
  • $\begingroup$ Sadly, I am not able to get hold of the first edition of Random Graphs (I have the 2nd edition though) $\endgroup$ – Vivek Bagaria Oct 30 '13 at 21:12

Your Answer

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

Browse other questions tagged or ask your own question.