<p><a href="http://www.ams.org/journals/proc/1981-083-02/S0002-9939-1981-0624948-6/S0002-9939-1981-0624948-6.pdf">Bollobas</a> showed that for any $d$ and any $g$, there exists a $d$-regular graph $G$ of girth at least $g$ such that </p>

<p>$$
\alpha(G) &lt; \frac{2n\log d}{d}.
$$</p>

<p>So you cannot hope for more than a factor 16 improvement. <a href="http://cs.anu.edu.au/~Brendan.McKay/papers/IndSetsRegGraphs.pdf">McKay</a> gave somewhat sharper bounds.</p>

CC BY-SA 3.0
2014-04-16T05:57:05.833Z
Are there any mild conditions which can be assumed to get a better bound for graphs with high girth?
Vivek Bagaria
CC BY-SA 3.0
2014-04-16T20:02:28.903Z
@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
CC BY-SA 3.0
2014-04-27T10:10:50.277Z
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
CC BY-SA 3.0
2014-04-15T15:43:40.323Z
2014-04-15T15:43:40.323Z
Sasho Nikolov
<p>For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true</p>

<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)}{8d}\log_2d.$$</p>

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

<p><strong>My Question :</strong> Are there extensions of above result for graphs with girth $\geq l$ ?</p>

CC BY-SA 3.0
2014-04-17T07:08:41.587Z
"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
CC BY-SA 3.0
2014-04-17T07:35:33.113Z
yes. I will do it.
Vivek Bagaria
<reference-request><graph-theory>
Independent set size of a large girth graphs
Vivek Bagaria
# Independent set size of a large girth graphs

(Asked by: username_0 on 2014-04-15)

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$ ?

**Tags:** reference-request, graph-theory
> **Comments:**
> **username_1**: "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?  
> **username_0**: yes. I will do it.  

---

## 1 answers

### Answer by username_2 on 2014-04-15. Score: 7

[Bollobas](http://www.ams.org/journals/proc/1981-083-02/S0002-9939-1981-0624948-6/S0002-9939-1981-0624948-6.pdf) 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](http://cs.anu.edu.au/~Brendan.McKay/papers/IndSetsRegGraphs.pdf) gave somewhat sharper bounds.

> **Comments:**
> **username_0**: Are there any mild conditions which can be assumed to get a better bound for graphs with high girth?  
> **username_2**: @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.  
> **username_0**: 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.  

---

