# Independent set size of a large girth graphs

For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true

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

$$\alpha(G) \geq \frac{n(G)}{8d}\log_2d.$$

Where $n(G)$ is the vertex size of the graph, $d$ is the avg degree and $\alpha(G)$ is the size of maximum independent set.

My Question : Are there extensions of above result for graphs with girth $\geq l$ ?

• "square-free" graphs are not the same as girth >= 5 graphs. Your title says "square-free" but your question does not. Perhaps change your title to reflect this? – JimN Apr 17 '14 at 7:08
• yes. I will do it. – Vivek Bagaria Apr 17 '14 at 7:35

## 1 Answer

Bollobas showed that for any $d$ and any $g$, there exists a $d$-regular graph $G$ of girth at least $g$ such that

$$\alpha(G) < \frac{2n\log d}{d}.$$

So you cannot hope for more than a factor 16 improvement. McKay gave somewhat sharper bounds.

• Are there any mild conditions which can be assumed to get a better bound for graphs with high girth? – Vivek Bagaria Apr 16 '14 at 5:57
• @Bagaria I am not aware of any. But I do not know the literature on the question very well. McKay's paper is concerned with getting exact bounds. It might be worth going into the probabilistic constructions which give the bounds. – Sasho Nikolov Apr 16 '14 at 20:02
• I have read above the paper by Bollobas and almost understood the proof. But, I am not able to understand the crux of the proof, which part of the proof is the most essential? Once that is understood, one could probably add a relevant constraint and improve the bound. – Vivek Bagaria Apr 27 '14 at 10:10