Largest size of a complete bipartite sub-graph in a random graph

Question

Let $G\in G(n,\frac{1}{2})$ be a random graph. What is the maximum number of edges of a complete bipartite graph that can appear as a subgraph in $G$ almost surely?

Let's give an estimate in the following. Please first note that:

1) It is not hard to see that $K_{a, a}$ does not appear in $G$ almost surely for any $a=2(1+\epsilon)\log_{2}{n}$ where $\epsilon > 0$.

2) Since the average degree of $G$ is around $\frac{n}{2}$. So, $G$ has $K_{1, \frac{n}{2}}$ as its subgraph almost surely.

In conclusion, if $K_{s,t}$ with the maximum number of edges appears in G almost surely with $s\leq t$, then $s$ must be less than $2(1+\epsilon)\log_{2}{n}$ and hense $\frac{n}{2}\leq st\leq 2n(1+\epsilon)\log_{2}{n}$ for every $\epsilon > 0.$

Answer 1

The best $K_{s,t}$ to choose occurs for $s=1$ or $s=2$, both of which allow a bit over $\frac n2$ edges.

Let's first consider the case when $s$ is a constant independent of $n$. For any fixed set of $s$ vertices, the probability that some other vertex is adjacent to all of them is $\frac1{2^s}$, so we expect that $t \approx \frac{n}{2^s}$ is the best we can do. As a weak bound, for all $\epsilon>0$ and for all constant $s$, with high probability $G$ does not contain a $K_{s,(1/2^s + \epsilon)n}$. More precisely, a choice of $O(n^s)$ starting vertices, for any constant $s$, lets us get to $t = \frac{n}{2^s} + O(\sqrt{n \log n})$, where the $O$ hides a constant depending on $s$. This is because the tail of the binomial decays like $e^{-x^2/n}$, which for $x = O(\sqrt{n \log n})$ becomes $n^{-O(1)}$.

Of all of these constant $s$, we get the most edges with $s=1$ or $s=2$, where $\frac{s}{2^s} = \frac12$. Taking $s=2$ may get us slightly more edges, but in both cases the number of edges in $K_{s,t}$ is $\frac{n}{2} + O(\sqrt{n \log n})$.

The above discussion assumed $s$ is a constant, letting us ignore the dependence on $s$ in the $O(\sqrt{n \log n})$ error term. Next, we rule out any large values of $s$.

Assume $s \le t$, and suppose we want at least $\frac n3$ edges in $K_{s,t}$. Then the probability of all those edges being there is at least $2^{-st} \le 2^{-n/3}$, so if the number of ways to choose the vertices of $K_{s,t}$ is not on the order of $2^{n/3}$, we don't have a chance.

For an upper bound, we can choose the $s+t$ vertices with replacement, which makes things simple, because since $s \le t$, we want there to be at least $2^{n/6}$ ways to pick the $t$ vertices. This requires taking $t \ge 0.04n$ or so, by bounds on $\binom{n}{pn}$. Having a $K_{s,0.04n}$ subgraph is already ruled out for $s=5$, since $\frac1{32} = 0.03125$, so we only need to consider $s=1,2,3,4$, which we've already done.