Link
GrpLib

This site uses Just the Docs, a documentation theme for Jekyll.

Canonical Images

Given a group $G$ acting on a set $S$, a Canonising function $f:S \mapsto S$ which satisfies two conditions:

  • $\exists g \in G. f(S) = S^g $.
  • $\forall s \in S, g \in G. f(S) = f(S^g) $.

Together these functions provide a way of checking if two items $s_1,s_2 \in S$ are in the same orbit of $G$.

While there are functions which check if $\exists g \in G. s_1^g = s_2$ directly, canonising functions are useful because given a large set $T \subseteq S$, we can use the canonical image of each element of $T$ to find equivalent subsets, while we would have to perform $|T|^2$ pair-wise checks if we could only check if two elements were in the same orbit.

Canonical image algorithms are usually defined by $S$, the objects which they can find the canonical image for.

Graphs

The most famous example of finding canonical image is graphs and digraphs. In this area Nauty (and it’s extension Traces) (McKay & Piperno, 2014) is the most famous system. Other systems such as Saucy (Darga et al., 2008), Bliss (Junttila & Kaski, 2007) and Conauto (López-Presa et al., 2011) implement different improvements and extensions to Nauty’s original algorithm.

Sets

The first published algorithm for finding the canonical image of a set under a group found the minimal image of the set in its orbit (Linton, 2004). Later algorithms have found other canonical images (Jefferson et al., 2019).

References

  1. Jefferson, C., Jonauskyte, E., Pfeiffer, M., & Waldecker, R. (2019). Minimal and canonical images. J. Algebra, 521, 481–506. https://doi.org/10.1016/j.jalgebra.2018.11.009
  2. Junttila, T., & Kaski, P. (2007). Engineering an efficient canonical labeling tool for large and sparse graphs. In D. Applegate, G. S. Brodal, D. Panario, & R. Sedgewick (Eds.), Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (pp. 135–149). SIAM.
  3. Linton, S. (2004). Finding the smallest image of a set. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, 229–234. https://doi.org/10.1145/1005285.1005319
  4. López-Presa, J. L., Anta, A. F., & Chiroque, L. N. (2011). Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation. CoRR, abs/1108.1060. http://arxiv.org/abs/1108.1060
  5. McKay, B. D., & Piperno, A. (2014). Practical graph isomorphism, II. Journal of Symbolic Computation , 60(0), 94–112. https://doi.org/10.1016/j.jsc.2013.09.003
  6. Darga, P. T., Sakallah, K. A., & Markov, I. L. (2008). Faster symmetry discovery using sparsity of symmetries. 2008 45th ACM/IEEE Design Automation Conference, 149–154.