Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$ ?
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.
