It's well known that a $C\_4$-free graph of order $n$ has average degree $O(\sqrt{n})$, and it [follows](https://math.stackexchange.com/questions/2419506/chromatic-number-of-a-graph-with-no-4-cycles) 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.



Independence number of $C_4$-free graphs
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.


