Impact
~792
people reached
- 0 posts edited
- 0 helpful flags
- 0 votes cast
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? |