most recent 30 from http://mathoverflow.net 2013-05-19T03:07:46Z http://mathoverflow.net/feeds/question/116091 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116091/expected-size-of-unbalanced-biclique-in-random-bipartite-graph Oliver 2012-12-11T15:10:05Z 2012-12-11T23:56:36Z

<p>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</p> <p><a href="http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra" rel="nofollow">http://mathoverflow.net/questions/115748/whats-an-upper-bound-on-the-size-of-the-largest-biclique-in-random-bipartite-gra</a></p> <p>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$. </p> <p>Let $E=E_1∪E_2$ be a biclique satisfying ${Expectation}(∣E_1∣) \leq {Expectation}(∣E_2∣)$. The conjecture is that</p> <pre><code>for all α&gt;0, Pr{∣E_1∣ is greater than α×n}→0 as n→∞. </code></pre> <p>Could any of you help me on this?</p> <p>Thanks a lot!</p> <p>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∣$). </p> <p>Oliver</p>

http://mathoverflow.net/questions/116091/expected-size-of-unbalanced-biclique-in-random-bipartite-graph/116128#116128 Ben Barber 2012-12-11T23:56:36Z 2012-12-11T23:56:36Z

<p>Thanks for the clarification. This set-up has enough flexibility that we can recover the star counterexample from before.</p> <p>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$.</p>