4
$\begingroup$

The (2-dimensional) Weisfeiler-Leman algorithm is a method for partitioning the ordered pairs of vertices of a graph in a canonical way which gives rise to a powerful graph invariant (see for instance Section 4 of this paper). If the partitions arising from two graphs are NOT "equivalent" in a certain sense, then the graphs cannot be isomorphic. However, there do exist graphs whose partitions resulting from the Weisfeiler-Leman algorithm are equivalent but are still non-isomorphic. The smallest such pair that I am aware of is the $4 \times 4$ rook graph (the Cartesian product of the complete graph $K_4$ with itself) and the Shrikhande graph. These are both strongly regular graphs with the same parameters, and any such pair of graphs are equivalent under the Weisfeiler-Leman algorithm. My question is, is this the smallest (in number of vertices) pair of non-isomorphic graphs that are equivalent under the Weisfeiler-Leman algorithm?

If we allow for directed graphs, then there are some strongly regular tournaments on 15 vertices that are equivalent under the Weisfeiler-Leman algorithm. Is there a smaller pair of non-isomorphic directed graphs that are equivalent under the Weisfeiler-Leman algorithm?

For what it's worth, this is the same as asking for the smallest pair of non-isomorphic graphs that admit an (weak) isomorphism between their coherent algebras that maps the adjacency matrix of the first graph to that of the second.

$\endgroup$
  • $\begingroup$ Okay, I thought I could put two bounties on the same question because of what I read here: meta.stackexchange.com/questions/2786/… but apparently that is not possible. $\endgroup$ – David Roberson Feb 2 '18 at 11:01
  • $\begingroup$ You probably might like to be more explicit about what exactly you mean by the invariant here. Note that you might start WL-algorithm with a regular graph and end up with "complete" coherent configuration, i.e. each edge and non-edge in an equivalence class of its own. I presume such examples are available for n<15 vertices. $\endgroup$ – Dima Pasechnik Feb 7 '18 at 0:31
  • $\begingroup$ One needs to look at loop/(directed)-edge class sizes at each iteration, not only at the final stage. $\endgroup$ – Dima Pasechnik Feb 7 '18 at 9:38
  • $\begingroup$ There are just two strongly regular tournaments on 15 vertices, one obtained from the other by reversing the orientation, and they are not isomorphic according to computer calculations. $\endgroup$ – Dima Pasechnik Feb 7 '18 at 11:10
5
+50
$\begingroup$

The 15-vertex "strongly regular" tournament is the smallest non-Schurian example of an association scheme; it is unique as an assoc. scheme (there is no Schurian scheme with these parameters - but see PS below!). The smallest case of two non-isomorphic association schemes with the same parameters needs 16 vertices. These were results of calculations I did over 30 years ago using a Fortran IV program written to enumerate association schemes---which is unfortunately lost. It was roughly following the "Russian school" methodology of enumeration of strongly regular graphs (and was a 2-year course work done under supervision of Igor Faradjev, one of pioneers of constructive enumeration).

These results were confirmed years later by a group in Japan---they wrote their own code to do this enumeration. Up-to-date tables are here.


PS. The smallest pair of non-isomorphic "strongly regular" tournaments indeed needs 15 vertices: in the corresponding (unique) association scheme there are two digraphs, obtained one from the other by reversing the orientation - but this operation is obviously not an isomorphism, and in fact there is no isomorphism (according to computer calculations using Sagemath).

$\endgroup$
  • $\begingroup$ Thanks Dima! Do you know if there is a smaller example if you consider non-isomorphic coherent configurations (instead of restricting to association schemes) that have the same parameters (I think this is sometimes called being "weakly isomorphic")? Also, do you have any idea of how computationally feasible it would be to say, compute all (isomorphism classes of) CCs on up to 24 points and find the weak isomorphisms between them? Based on the table you linked, this seems doable for association schemes, since there are not so many of them. $\endgroup$ – David Roberson Feb 6 '18 at 23:20
  • $\begingroup$ P.S. Did the Sage package for working with CCs mentioned here (www1.spms.ntu.edu.sg/~dima/pubs/cohcfg-shortnote.pdf) ever materialize? $\endgroup$ – David Roberson Feb 6 '18 at 23:24
  • $\begingroup$ Already enumerating association schemes is tricky, as you build tensors of multiplication coefficients as you go along, you don't have some kind of catalogue to get them from. The same technique would work for CCs, though. $\endgroup$ – Dima Pasechnik Feb 7 '18 at 0:43
  • $\begingroup$ While I only have some incomplete GAP package for CCs (lack of students to work on, etc, you know), other people have e.g. github.com/chpech/COCO2P $\endgroup$ – Dima Pasechnik Feb 7 '18 at 0:48
  • $\begingroup$ Do you happen to have a good reference for a more in depth description of how to enumerate association schemes? $\endgroup$ – David Roberson Feb 7 '18 at 21:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.