Maximum size of a bipartite subgraph on a random graph Show that almost every $G \in \mathscr{G}(n,\frac{1}{2})$ contains no bipartite subgraph with more than $\frac{n^2}{8} + n^{\frac{3}{2}}$ edges.
Tried using Markov's inequality by setting a = $\frac{n^2}{8} + n^{\frac{3}{2}}$, but I got that the probability is less than or equal to 1, which doesn't help.
By almost every $G$ I mean that as $n$ tends to infinity the probability of the bipartite subgraph having more than $\frac{n^2}{8} + n^{\frac{3}{2}}$ edges tends to 0.
May have something to do with finding a threshold function for bipartite graphs (might not).
 A: We may as well assume that every vertex of $\mathscr G(n,1/2)$ is included in the bipartite subgraph: leaving a vertex out can only decrease the number of edges. That way, there are $2^n$ possible bipartitions, each with at most $\frac{n^2}{4}$ potential edges.
For a given bipartition, the number of edges the corresponding bipartite graph actually has is binomial: $\text{Binomial}(\frac{n^2}{4}, \frac12)$. So we can bound the probability by using the Chernoff bound. The value $\frac{n^2}{8} + n^{3/2}$ is $\left(1 + \frac{8}{\sqrt n}\right) \frac{n^2}{8}$, so we have
$$\Pr\left[\text{Binomial}\left(\frac{n^2}{4}, \frac12\right) > \frac{n^2}{8} + n^{3/2}\right] \le \exp\left(-\frac13 \left(\frac{8}{\sqrt n}\right)^2 \frac{n^2}{8}\right) = e^{-8n/3}.$$
Some bipartitions will have fewer potential edges, but for them this is also an upper bound.
So the expected number of bipartitions with this many edges is at most $2^n e^{-8n/3} = (2 e^{-8/3})^n$, and because $2^3 < e^8$ this goes to $0$ as $n \to \infty$. By the union bound, this means that with probability tending to $1$ no bipartition of the random graph (and therefore no bipartite subgraph of the random graph) will have this many edges.
