4
$\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 node on side $R$ is connected to $k$ nodes on side $L$, that $|R| < k< |L|$, and that $k$ is much larger than $|R|$.

What is the minimal size (i.e., number of edges) of the maximal biclique1?

1maximal biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.

Improve this question
$\endgroup$
4
  • $\begingroup$ would you please state what $\ll$ is supposed to mean here? Also: I, and I think, many others, would prefer the capital letter $K$ be replaced with $k$. (The latter is 'mere' tradition of course, i.e. to try to have notation and capitalization reflect the types of objects.) @ Daniel Soudry $\endgroup$
    – Peter Heinig
    Commented Aug 9, 2017 at 14:45
  • $\begingroup$ Sure, I've edited the question to modify and clarify notation like you asked. in other words "$\ll$" is just an inequality in which one side is much larger than the other side. $\endgroup$
    – Daniel Soudry
    Commented Aug 9, 2017 at 15:11
  • $\begingroup$ @DanielSoudry I expect that by $|R| \ll k$ you mean that $R$ is "much smaller than $k$". Is that right? $\endgroup$
    – Dan Cranston
    Commented Aug 9, 2017 at 21:27
  • $\begingroup$ Yes, clarified (I guess I am still thinking about inequalities in my native right-to-left language). $\endgroup$
    – Daniel Soudry
    Commented Aug 10, 2017 at 5:04

1 Answer 1

Reset to default
1
$\begingroup$

It seems the answer is 2. Start with a disjoint union of stars, each with the center in $R$ and $k$ leaves in $L$. Now pick two of those stars and identify a single leaf in each. You get a copy of $K_{2,1}$ that is a maximal biclique. (It is certainly not maximum, but that is not what was asked.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry, I don't follow: 1) What is $K_{2,1}$ and what did you mean by "copy"? 2) Why is this a biclique (i.e., complete biparatite subgraph)? Thanks! $\endgroup$
    – Daniel Soudry
    Commented Aug 10, 2017 at 8:39
  • $\begingroup$ @DanielSoudry In general $K_{a,b}$ means a bipartite graph with $a$ vertices on one side, $b$ vertices on the other side, and all possible edges between the two sides. So $K_{2,1}$ is simply a path on 3 vertices. By "copy of $K_{2,1}$" I mean that $K_{2,1}$ appears as a subgraph. From the definition of $K_{2,1}$ now it should be clear that this is a biclique. It is maximal because those two centers with a common neighbor have no other common neighbors and their common neighbor has no other neighbors at all. $\endgroup$
    – Dan Cranston
    Commented Aug 10, 2017 at 14:10
  • $\begingroup$ Oh, I see it wasn't clear to me that "identify" means that both stars have only one common leaf. I see your point now. I'll open another question on "maximum", and give you the answer... Thanks! $\endgroup$
    – Daniel Soudry
    Commented Aug 10, 2017 at 17:00
  • $\begingroup$ Wait, but this is not true if there is too much unavoidable overlap. For example, if $|R|=2, k=5, |L|=6$ then the minimal maximal bicluque has size $2×4=8$. @Dan Cranston $\endgroup$
    – Daniel Soudry
    Commented Aug 11, 2017 at 4:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .