30 reputation
3
bio website
location
age
visits member for 2 years
seen Feb 8 '13 at 0:11

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?