1
$\begingroup$

We have a random bipartite graph $G=(V,U,E)$ and $|V|=|U|=n$, in which any vertex pair $<v,u>$ ($v\in V$,$u\in U$) exists an edge with probability $p$. A balanced bipartite complete graph is a biclique $G(X,Y,E)$ that $|X|=|Y|$ and $E=X\times Y$ . So, does somebody have an idea about how to estimate the distribution of maximum size of balanced biclique?

Improve this question
$\endgroup$
4
  • $\begingroup$ Edge exists with which probability? $\endgroup$
    – Fedor Petrov
    Commented Mar 31, 2016 at 21:46
  • 1
    $\begingroup$ Looks like standard second-moment method. $\endgroup$
    – Brendan McKay
    Commented Mar 31, 2016 at 22:21
  • 1
    $\begingroup$ @joey: Perhaps better ask this question on math.stackexchange.com ? $\endgroup$
    – Moritz
    Commented Mar 31, 2016 at 22:31
  • $\begingroup$ @FedorPetrov , sorry, probability $0<p<1$ $\endgroup$
    – joey
    Commented Apr 1, 2016 at 8:00

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .