4
$\begingroup$

I am not an expert in random graph but I need the following result and I couldn't find any reference on this.

Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup Y$, $X$ and $Y$ both have cardinality $n$ and $p$ is the proba of adding an edge between each node in $X$ and each node in $Y$. $p \in (0,1)$ is independent of $n$. I am interested in the (expected) size of the largest biclique (not necessarily balanced!). To be more precise, a set $E_1 \cup E_2$, $E_1 \subset X$ and $E_2 \subset Y$ is a biclique if for each node $x \in X$ and each node $y \in Y$, there is an edge between $x$ and $y$. The size of a biclique $E_1 \cup E_2$ is $\mid E_1 \mid + \mid E_2 \mid$.

Let $E$ be a biclique. The conjecture is that

  • for all $\alpha>0$, Pr{E has size greater than $\alpha \times n$}$\rightarrow 0$ as $n \rightarrow \infty.$

I guess there exist references on this or standard way to prove this. Could any of you help me on this?

Thanks a lot!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

For every vertex $x$ in $G$, have $\:\text{star}(x)\:$ denote the set whose members are $x$ and the vertices adjacent to $x$.
For every vertex $x$ in $G$, $\:\text{star}(x)\:$ is a biclique of size $\:\text{deg}(x)+1\;$. $\;\;$ The degrees of vertices in
$X$ are independent and distributed as $\:\text{Bin}(n,p)\;$. $\;\;$ From the central limit theorem, if $\: \alpha \leq p$
then for sufficiently large $n$, the probability that any particular vertex's star is not a biclique of
size greater than $\: \alpha \cdot n \:$ will be less than $\frac23$. $\;\;$ If $\: \alpha \leq p \;$ then as $n$ goes to infinity the probability
that no star centered on a vertex in $x$ is a biclique of size greater than $\: \alpha \cdot n \:$ converges to $0$.

Therefore, if $\: \alpha \leq p \;$ then $\;\;\;\; \displaystyle\lim_{n\to \infty} \: \text{Pr}\hspace{.01 in}(\text{the graph a a biclique with size greater than } \alpha \cdot n) \;\; = \;\; 1 \;\;\;\;\;$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ thanks a lot for the prompt answer. I now clearly see that I was wrong! $\endgroup$
    – Oliver
    Dec 7, 2012 at 22:54
  • 1
    $\begingroup$ If only bicliques whose two parts have similar size are allowed, the expected maximum is much less: only logarithmic like cliques in ordinary random graphs. $\endgroup$
    – Brendan McKay
    Dec 8, 2012 at 4:04
  • $\begingroup$ I see, thanks a lot! (I actually just saw your answer) So if $E_1 \cup E_2$ is a biclique and if in addition $E_1 \leq E_2$, then for any \alpha>0, Pr{E_1 has size greater than \alpha n)->0 as n->\infty. (let me state it in that way even if we could get something better in terms of log) Now, what would be enough for me is actually a slightly weaker result, i.e., the same result but which would only assume that the expectation of $E_1$ is smaller than the expectation of E_2$. Do you have any ideas if this holds / is known? Thanks again for your help. Oliver $\endgroup$
    – Oliver
    Dec 10, 2012 at 21:17
  • $\begingroup$ Of course, when I write $E_i$ above, this should be understood as the cardinality of $E_i$ -- sorry for the imprecision. $\endgroup$
    – Oliver
    Dec 10, 2012 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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