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

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.$$

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.

• Thank you very much for your time. Also, I just wanted to know is there any research paper known about this question? – 123... Dec 18 '18 at 9:02
• Not that I'm aware of. It seems like something more likely to come up in the process of solving some other problem rather than on its own, so I can't say whether people have or haven't looked at this question before. – Misha Lavrov Dec 18 '18 at 15:32
• Thanks for your comment. I truly appreciate it. – 123... Dec 18 '18 at 17:54