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.

  • $\begingroup$ Thank you very much for your time. Also, I just wanted to know is there any research paper known about this question? $\endgroup$ – 123... Dec 18 '18 at 9:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Misha Lavrov Dec 18 '18 at 15:32
  • $\begingroup$ Thanks for your comment. I truly appreciate it. $\endgroup$ – 123... Dec 18 '18 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.