2
$\begingroup$

We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each vertex on side $R$ is connected to $k$ vertices on side $L$, and that $|R| < k< |L|$.

I'm interested in the regime in which $k /|R| \rightarrow \infty$, $|L|/(|R|(|L|-k)) \rightarrow 0$ and $k/ |L| \rightarrow 1 $ . Note that this implies that each vertex in $R$ is connected to almost all the vertices in $L$.

Question: What is the minimal size (i.e., number of edges) of the maximum biclique1?
The answer should depend on all constants: $|R|,|L|$ and $ k$ .

Note that a greedy approach (adding vertices one by one in $R$) naively gives $|L|^2/(4(|L|-k))$. However, I'm looking for a better solution, if one exists.

1 Maximum biclique: The largest (in terms of number of edges) complete bipartite subgraph. Not to be confused with a maximal biclique.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ So what if you take the disjoint union of some stars, i.e., $K_{1,k}\cup \ldots\cup K_{1,k}$? The minimum size of a maximum biclique will be $k$ and this clearly can't be beaten. $\endgroup$
    – domotorp
    Commented Aug 10, 2017 at 19:43
  • $\begingroup$ The problem is that it is not possible for stars to be disjoint if $k$ is too large. For example if $|L|-1=k$. $\endgroup$
    – Daniel Soudry
    Commented Aug 11, 2017 at 4:30
  • $\begingroup$ So do you expect an answer as a function of not only $k$, but also of $|L|$ and $|R|$? $\endgroup$
    – domotorp
    Commented Aug 11, 2017 at 11:26
  • 1
    $\begingroup$ I doubt that we may in general get anything better than $k$ edges (achieved for a trivial biclique with 1 vertex in $R$ and $k$ vertices in $L$), only for $k$ close to $L$. Indeed, in order to beat this bound, you should have some $m$ vertices in $R$ having more than $k/m$ common neighbours in $L$. But If you choose $R$ subsets of neighbours at random, the probability of such event is small for reasonably large $L$. $\endgroup$
    – Fedor Petrov
    Commented Aug 12, 2017 at 9:14
  • 1
    $\begingroup$ If you believe the random intuition then you're looking to maximise $a(1-\delta)^a |L|$, with $k = (1-\delta)|L|$. A maximum of around $|L| / \delta e$ is achieved near $a = 1/\delta$, which is your greedy bound with $4$ replaced by $e$. $\endgroup$
    – Ben Barber
    Commented Aug 28, 2017 at 10:56

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .