Oliver
Reputation
Top tag
Next privilege 50 Rep.
Comment everywhere
 Feb 6 asked expected number of cycles in a “random” bipartite directed graph Dec 12 accepted expected size of unbalanced biclique in random bipartite graph Dec 12 comment expected size of unbalanced biclique in random bipartite graph Thanks a lot Ben. This makes perfect sense! Dec 11 comment expected size of unbalanced biclique in random bipartite graph 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... Dec 11 revised expected size of unbalanced biclique in random bipartite graph added 3 characters in body Dec 11 awarded Editor Dec 11 revised expected size of unbalanced biclique in random bipartite graph added 8 characters in body Dec 11 comment expected size of unbalanced biclique in random bipartite graph 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? Dec 11 asked expected size of unbalanced biclique in random bipartite graph Dec 10 comment what's an upper bound on the size of the largest biclique in random bipartite graph? Of course, when I write $E_i$ above, this should be understood as the cardinality of $E_i$ -- sorry for the imprecision. Dec 10 comment what's an upper bound on the size of the largest biclique in random bipartite graph? 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 Dec 8 awarded Student Dec 7 awarded Scholar Dec 7 comment what's an upper bound on the size of the largest biclique in random bipartite graph? thanks a lot for the prompt answer. I now clearly see that I was wrong! Dec 7 accepted what's an upper bound on the size of the largest biclique in random bipartite graph? Dec 7 asked what's an upper bound on the size of the largest biclique in random bipartite graph?