A well known off-diagonal Ramsey result says that every $C\_3$-free graph $G$ on $N$ vertices has an independent set of size $\Omega(\sqrt{N\log N})$.


It is a conjecture of Erdos that every $C\_4$-free graph $G$ on $N$ vertices has an independent set of size $\Omega(N^{1/2+c})$ for some absolute constant $c>0$.


My question is: is there some $g$ where we know that any $N$-vertex graph $G$ without any copies of $C\_3,C\_4,\dots,C\_{g-1}$ has an independent set of size $\Omega(N^{1/2+c})$ for some $c>0$?



Independent sets in graphs with girth $\ge g$
Yes, and for any $c<1/2$. Namely, for $\delta>0$ assume that our graph does not have an independent set of size $N^{1-\delta}$. In particular this yields that the chromatic number is at least $N^{\delta}$, thus there is an induced subgraph $H$ with all degrees at least $N^{\delta}$ (proof: remove vertices of smaller degree while they exist, this does not affect the large chromatic number). Then if you consider the neighborhood of arbitrary vertex $v$, you get that it has at least $N^{\delta}$ neighbours, they in turn have at least $N^\delta(N^\delta-1)$ neighbours, and all these guys are distinct if $G$ does not contain $C\_3$ and $C\_4$, they have at least $N^\delta(N^\delta-1)^2$ new neighbours which are all distinct if the graph does not contain also $C\_5$ and $C\_6$, etc. On step about $1/\delta$ you get too many vertices.


