0
$\begingroup$

I am discovering random graph and I am trying to prove the following result. This is a follow-up on a previous question of mine

what's an upper bound on the size of the largest biclique in random bipartite graph?

Let G(X∪Y,p) be a random bipartite graph where the set of vertices is X∪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∈(0,1) is independent of $n$. A set $E_1∪E_2$, $E_1⊂X$ and $E_2⊂Y$ is a biclique if for each node $x∈X$ and each node $y∈Y$, there is an edge between $x$ and $y$.

Let $E=E_1∪E_2$ be a biclique satisfying ${Expectation}(∣E_1∣) \leq {Expectation}(∣E_2∣)$. The conjecture is that

for all α>0, Pr{∣E_1∣ is greater than α×n}→0 as n→∞.

Could any of you help me on this?

Thanks a lot!

If instead of requiring ${Expectation}(∣E_1∣) \leq {Expectation}(∣E_2∣)$, I were to focus on balanced biclique, i.e., require $∣E_1∣ = ∣E_2∣$, then the result is already known. Clearly, the result would also hold if I were to assume that $∣E_1∣ \leq ∣E_2∣$ (given that from such a biclique, I could "extract" a balanced biclique of size $∣E_1∣$).

Oliver

Improve this question
$\endgroup$
5
  • $\begingroup$ I'm having trouble parsing "Let $E$ be a biclique satisfying $\mathbb{E}(|E_1|) \leq \mathbb{E}(|E_2|)$." Could you perhaps clarify what you mean? $\endgroup$
    – Ben Barber
    Commented Dec 11, 2012 at 16:12
  • $\begingroup$ Sure. I am not entirely sure this makes sense but what I wanted is to consider $E=E_1 \cup E_2$ where E is a biclique -- E is a random variable and, hence, so are $E_1$ and $E_2$. So I wanted to impose the constraint on those r.v. that $Expectation(|E_1|)≤Expectation(|E_2|)$ and hence restrict my attention only to bicliques $E=E_1 \cup E_2$ having the property that $Expectation(|E1|)≤Expectation(|E2|)$. Does this answer? $\endgroup$
    – Oliver
    Commented Dec 11, 2012 at 17:35
  • $\begingroup$ "$E$ is a random variable": How is $E$ determined from the random graph? $\endgroup$
    – Ben Barber
    Commented Dec 11, 2012 at 21:55
  • $\begingroup$ For each realization of the random (bipartite) graph, one can pick an arbitrary E which is a biclique. By definition, $E=E_1 \cup E_2$. Seen as a random set, E defines my r.v. Of course, there are plenty of different r.v. to be considered (depending on which one we pick above). The only constraint I would like to impose is that $Expectation(|E_1|)≤Expectation(|E_2|)$. I'd like the statement in the Question to be true for all such r.v. E (i.e., for all α>0, Pr{∣E_1∣ is greater than α×n}→0 as n→∞). Hope this answers... $\endgroup$
    – Oliver
    Commented Dec 11, 2012 at 22:11
  • $\begingroup$ cross-posted to math.stackexchange.com/questions/256598 $\endgroup$
    – joriki
    Commented Dec 12, 2012 at 16:25

1 Answer 1

Reset to default
0
$\begingroup$

Thanks for the clarification. This set-up has enough flexibility that we can recover the star counterexample from before.

Almost every random graph has a vertex in each class of degree about $pn$. So we can almost always choose $E$ to be a large star, and we can ensure the centre of the star is in each class about equally often. Then the expectations of the class sizes are almost equal, so with a bit of tweaking we satisfy the condition on the choice of $E$; but $E_1$ will be too large with probability almost $1/2$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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