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.

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 2018 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, 2018 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, 2018 at 11:10

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
6
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 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.