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$
5
  • $\begingroup$ See the end of my answer here: mathematica.stackexchange.com/a/109437/12 $\endgroup$
    – Szabolcs
    Apr 5, 2016 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$ Apr 5, 2016 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, 2016 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, 2016 at 12:28
  • 1
    $\begingroup$ Just for the record, this can still be reproduced in 11.0. $\endgroup$ Sep 15, 2016 at 8:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.