New constructions of bipartite graphs on \(m\), \(n\) vertices with many edges and without small cycles (Q1328391)

For arbitrary odd prime power \(q\) and \(s\in(0,1]\) such that \(q^ s\) is an integer, we construct a doubly-infinite series of \((q^ 5,q^{3+s})\)-bipartite graphs which are biregular of degrees \(q^ s\) and \(q^ 2\) and of girth 8. These graphs have the greatest number of edges among all known \((n,m)\)-bipartite graphs with the same asymptotics of \(\log_ nm\), \(n\to\infty\). For \(s={1\over 3}\), our graphs provide an explicit counterexample to a conjecture of Erdős which states that an \((n,m)\)-bipartite graph with \(m=O(n^{2/3})\) and girth at least 8 has \(O(n)\) edges. This conjecture was recently disproved by \textit{D. de Caen} and \textit{L. A. Székely} [Colloq. Math. Soc. János Bolyai 60, 135-142 (1992; Zbl 0795.05083)], who established the existence of a family of such graphs having \(n^{1+1/57+o(1)}\) edges. Our graphs have \(n^{1+1/15}\) edges, and so come closer to the best known upper bound of \(O(n^{1+1/9})\).