1
$\begingroup$

Inspired by yode's latest question I was playing around with RelationGraph and found that BipartiteQ seems to be unable to detect certain bipartite results.

As an example, I was looking at the graph where each vertex is a 1- or 2-digit integer, and edges indicate whether a 2-digit integer starts or ends with a 1-digit integer. This is clearly a bipartite graph (and GraphLayout -> "BipartiteEmbedding" shows this), since there are no edges between 2-digit numbers and no edges between single digits. And up to n = 19 this works fine:

g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
   && # != #2 &, ToString /@ Range[0, 19], 
 GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]

enter image description here

BipartiteGraphQ @ g
(* True *)

But as soon as I get to 20:

g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
   && # != #2 &, ToString /@ Range[0, 20], 
 GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]

enter image description here

BipartiteGraphQ @ g
(* False *)

The problem seems to be something internal to the result of RelationGraph, since extracting the edges and reconstructing the graph works:

BipartiteGraphQ @ Graph @ EdgeList @ g
(* True *)

We can however localise the problem a bit by computing the graph on a smaller set of vertices. It's possible to remove all but 6 vertices/edges and still reproduce the problem:

g = RelationGraph[(StringEndsQ[#1, #2] || StringStartsQ[#2, #])
   && # != #2 &, ToString /@ {0, 1, 2, 10, 12, 20}, 
 GraphLayout -> "BipartiteEmbedding", VertexLabels -> "Name"]

enter image description here

BipartiteGraphQ @ g
(* False *)

Removing any further edges "resolves" the problem.

Is this a bug in BipartiteGraphQ? Am I misunderstanding something about bipartite graphs?

I'm using Mathematica 10.4 on Windows 10.

$\endgroup$
  • $\begingroup$ See the end of my answer here: mathematica.stackexchange.com/a/109437/12 $\endgroup$ – Szabolcs Apr 5 '16 at 12:01
  • $\begingroup$ @Szabolcs Ah okay, so it's a known issue. Interestingly, in all the cases I've tried, GraphLayout -> "BipartiteEmbedding" still worked without an issue. $\endgroup$ – Martin Ender Apr 5 '16 at 12:04
  • $\begingroup$ BTW I reported that as CASE:3531918 on Feb 13 and they told me that the problem was already known. I didn't read your post in detail and I don't know if it is the same bug. I also complained here: chat.stackexchange.com/transcript/2234?m=27550013#27550013 $\endgroup$ – Szabolcs Apr 5 '16 at 12:06
  • $\begingroup$ BTW IGraph/M has IGBipartiteQ precisely for this reason. <del>But you should know that it is much slower than the built-in function because converting a Mathematica graph to an igraph one is a huge overhead.</del> ... Well, I just tested, and for huge graphs it is in fact faster than BipartiteGraphQ despite that conversion overhead!! $\endgroup$ – Szabolcs Apr 5 '16 at 12:28
  • 1
    $\begingroup$ Just for the record, this can still be reproduced in 11.0. $\endgroup$ – Martin Ender Sep 15 '16 at 8:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.