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
    Commented 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
    Commented 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
    Commented 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
    Commented Dec 10, 2012 at 22:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .