Independence number of $C_4$-free graphs It's well known that a $C_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it follows that the independence number is $\Omega(\sqrt{n})$.
This bound cannot be improved over $\Theta(n^{\frac34})$: A polarity graph of a projective plane of order $q$ has order $q^2+q+1$,degree $q+1$ and minimum eigenvalue $-\sqrt q$, so by the Hoffman bound, the independence number is at most $O(q^\frac32)=O(n^\frac34)$.
Question: Is it possible to get better bounds like $\alpha(G)=\Omega(|G|^a)$ with $a>\frac12$?
Any answer giving proof or disproof about whether it is possible to attain $a=\frac58$ would be accepted.
 A: If we denote $m=\alpha(G)+1$, then our graph does not contain $C_4$ and its complement does not contain $K_m$, thus $n<R(C_4,K_m)$ (and viceversa, if $n<R(C_4,K_m)$, there exists a graph on $n$ vertices without $C_4$ such that $\alpha(G)\leqslant m-1$). So this question is about $C_4$ and $K_m$ Ramsey number. J. Spencer (Asymptotic Lower Bounds for Ramsey Functions. Discrete Mathematics. 20 (1977), 69-76) proved that $R(C_4,K_m)\geqslant m^{3/2-o(1)}$, providing an example of the graph with $n$ vertices without $C_4$ and with $\alpha(G)\leqslant n^{2/3+o(1)}$. The currently best lower bound is, as far as I know, $R(C_4,K_m)\leqslant m^{2-o(1)}$ (see Y. Caro, Y. Li, C. C. Rousseau, and Y. Zhang. Asymptotic bounds for some bipartite graph - complete graph Ramsey numbers. Discrete Mathematics. 220 (2000), 51-56) that results in $\alpha(G)\geqslant n^{1/2+o(1)}$, there are some log improvements with respect to $n^{1/2}$ bound from OP). Since $5/8$ lies between $2/3$ and $1/2$, your question seems to be open.
