$K_{4k^2,4k^2}$ contains a subgraph with no $C_4$ and average degree at least $k$. Let $k$ be a positive integer. Prove that the complete bipartite graph $K_{4k^2,4k^2}$ contains a subgraph with no cycles of length $4$ and with average degree at least $k$.
I could do $K_{4k^3,4k^3}$ by using the probabilistic method but haven't been able to do $K_{4k^2,4k^2}$ so far.
 A: I propose this approach to solving this problem.
Let $p$ be an arbitrary prime number. Consider the affine plane $P=\mathbb{Z}_p\times\mathbb{Z}_p$.
It is known that each line contains $p$ points and $p+1$ lines pass through each point.
No more than one line passes through any two points of $P$ and any two lines have at most one common point.
Denote by $L$ the set of all lines. Clearly, $|P|=p^2$ and $|L|=p^2+p$.
Now consider the graph $G$ whose vertices are $P\cup L$. A point of $v\in P$ is connected to the line $u\in L$ if the point $v$ lies on the line $u$.
We obtain a bipartite graph $G$. A graph $G$ has $2p^2+p$ vertices. Each vertex of $P$ has degree $p+1$ and each vertex of $L$ has degree $p$.
Next, graph $G$ contains no cycles of length $4$. If $v_1u_1v_2u_2$ is a cycle of length $4$ and $v_1,v_2\in P$, $u_1,u_2\in L$, then $v_1,v_2\in u_1\cap u_2$.
Now let $k$ be given. Choose a prime number $p$ such that $k\leq p<2k$ (see Bertrand's postulate). Then $p\leq2k-1$ and $p^2+p<4k^2$. Therefore graph $G$ is a subgraph of $K_{4k^2,4k^2}$.
