The problem I'm dealing is the following:
Prove that for each $n$ exists a bipartite graph without $K_{2,2}$ subgraph and $\Omega(n^{4/3})$ edges.
I wanted to solve this using probability:
Start with two parts of size $n$ and add an edge with probability $p$ between parts. Then the expected number of $K_{2,2}$ subgraphs is $\binom{n}{2}^\binom{n}{2}p^4$ and we will remove one edge from each of these to obtain a $K_{2,2}$-free graph $G'$.
Expected number of edges in $G'$ is $n^np - \binom{n}{2}^\binom{n}{2}p^4$. My problem is that I don't know how to make this be in $\Omega(n^{4/3}$? Can I just set $p= 1/n^{(3n-4)/3}$? I am not really comfortable with these asymptotic notations so I don't get how to approach this.
Hint
As Misha mentioned in a comment, the expected number of edges added should be $n\cdot n\cdot p=n^2p$, while the expected number of edges removed should be $\binom n2 \cdot \binom n2 \cdot p^4$. To make things simpler, we use the approximation $$ \binom n2\approx \frac{n^2}2, $$ which is valid since we only care about getting $\Omega(n^{4/3})$ edges, and $\binom n2$ and $n^2/2$ have the same asymptotic growth. Therefore, the expected number of edges remaining is asymptoticallly $$ n^2p - \tfrac14 n^4 p^4, $$ so you just need to choose $p$ so that the above grows at least as quickly as $n^{4/3}$. As a further hint, consider choosing $p\propto n^{-\alpha}$, for some real number $\alpha$.