Chapter 8: Isotopisms and autotopisms

• Homotopy, isotopy
• Set of ordered triples of a quasigroup
• Topisms via graphs
• Implementation in GAP
• Graph Isomorphism (GI) problem

Homotopisms

Definition Let and be two right quasigroups. Let be mappings such that

holds for all . Then the triple is called a homotopism from to .

• We use the "right upper" notation for mappings
• The definition is fine for arbitrary magmas
• are the components of the homotopism
• Homotopisms can be composed component-wise
• Homotopisms with are precisely the homomorphisms

Isotopisms

Definition Let and be two right quasigroups. Let be mappings such that

holds for all . Then the triple is called a homotopism from to .

• The most important case is when are bijections
• Then, we speak of an isotopism
• Isotopisms with are precisely the isomorphisms
• From now on:
  • Only isotopisms!!
  • No homotopisms!! No paratopisms!!

Isotopy

• The notion of isotopy is motivated by geometry
• Isotopisms can be composed
• Isotopy is an equivalence relation
• Isotopisms for latin squares mean permuting the rows, columns and symbols

Homotopism objects in GAP

gap> Q1 := ProjectionRightQuasigroup( 3 );;
gap> Q2 := ProjectionRightQuasigroup( 2 );;
gap> f := Transformation( [1,1,2] );; 
gap> g := Transformation( [2,1,2] );; 
gap> h := f;;
gap> t := HomotopismRightQuasigroups( Q1, Q2, f, g, h );
<homotopism of right quasigroups>

• Homotopism, isotopisms and autotopisms are special GAP categories, following their mathematical build-up
• Their arithmetics has been speeded up by some GAP magic

Defining new isotopes

• One can use the formula
  to define new right quasigroups
• More precisely:

  Claim Let be a right quasigroups, a set, and bijections. Define the operation "" on by

  Then is a right quasigroup, isotopic to .

• We call the isotope of by .

Action on triples of right quasigroups

• Isotopisms do not act on elements
• Isotopisms act on triples:

• We define the ordered triple set
  of the right quasigroup
• is a subset of cardinality in
• Remark 1: If the underlying set or the operation is obvious from the context, then we may write or
• Remark 2: In the context of orthogonal arrays, is the set of rows of the , associated to

Characterization of isotopisms via ordered triples

Lemma The first two coordinates uniquely determines an element of

Theorem T (for "triples") Let , be right quasigroups and be bijections. Then is an isotopism iff it maps the set to .

Proof By the Lemma,

Autotopisms via ordered triples

• We denote by the set of bijections of onto itself
• acts on

Corollary to Theorem T The autotopism group of is the set-wise stabilizer of in

• The problem we have to solve:

  Given group , acting on the set . Given a subset of . Find the set-wise stabilizer subgroup of in

• Bad news: If , and are large, then it has no easy solution

Example

• consists of the identity and the transposition
• has order 8
• Beside the identity , is left invariant by the triples

• The autotopism group has order 4

Vertex-colored graphs

• We deal with simple graphs: no multiple edges and no loops
• Edges are 2-element subsets
• ,
• A vertex-coloring with colors is a map

• We say that the vertex has color
• are the color classes ()
• A vertex coloring with colors is equivalent with an ordered partition
  of the vertices, with (possibly empty) parts

Isomorphisms of vertex-colored graphs

• Let and be two simple graphs with -colorings
• An color-preserving isomorphism of two vertex-colored graphs is a bijective map , such that
  for all .
• In other words, maps the th color class to the th color class
• The automorphism group of a vertex-colored graph consists of color-preserving automorphisms
• Your favorite vertex coloring: degree

Vertex-colored graph of a right quasigroup

• Let be a right quasigroup
• Define the sets and as

• Put as set of vertices
• There are no vertices in and in
• The triple is connected to the vertex if and only if

• We denote the vertex -colored graph by

Topisms via graphs

Recall:

Theorem T (for "triples") Let be bijections. Then is an isotopism iff it maps the set to .

Theorem G (for "graphs") Two right quasigroups are isotopic if and only if the associated vertex 4-colored graphs are isomorphic.

Corollary to Theorem G The autotopism group of a right quasigroup is isomorphic to the automorphism group of the associated vertex 4-colored graph.

• The method is explicit: A graph ismorphism
  maps to , hence induces the map .

Implementation in GAP

gap> LoadPackage( "RightQuasigroups", false );
true
gap> q := RightBolLoop( 16, 3 );
RightBolLoop( 16, 3 )
gap> ag := AutotopismGroup( q );
<group with 5 generators>
gap> Size( ag );
768

• There are several GAP packages for graphs, most importantly GRAPE and Digraphs
• In the present version, we use Digraphs, but this may change later

  gap> KnownAttributesOfObject( q );
  [ "Name", "Size", ... , "AutotopismGroup", "RQ_Digraph" ]
  gap> RQ_Digraph( q );
  <immutable digraph with 304 vertices, 768 edges>
  

Graph Isomorphism (GI) problem

The following problems are (essentially) equivalent:

• Given two simple graphs. Decide if they are isomorphic.
• Given two simple graphs. Find an isomorphism or return fail
• Given two simple graphs with vertex colorings. Find a color-preserving isomorphism or return fail
• Given a simple graph. Find a generating set of its automorphism group.

  ---

• Theoretical result:

  Theorem (L Babai, 2015) GI has quasi-polinomal time complexity.

• Quasi-polynomial means

Canonical labelings of graphs

Definition A canonical isomorph function assigns to every graph an isomorph such that whenever is isomorphic to we have . We call the canonical isomorph of .

Definition A canonical labeling function assigns to every graph a permutation such that the map

is a canonical isomorph function. We call the canonical labeling of .

• In computation, the vertex set of all graphs are assumed to be
• Hence, a canonical labeling is a permutation of degree .

  ---

• Good practice: Graph aut group <=> canonical labeling => graph isomorhism

Canonical Labeling Algorithm

• The algorithm and its first implementation is due to Brendan McKay
• 1978-1981, improved continuously
• nauty (No AUTomorphism, Yes?)
• Recent reimplementation: Bliss
• Other attempts: saucy, conauto, Traces
• Traces by Piperno is distributed with nauty since 2014
• SageMath, GAP and Magma interfaces

Complexity of canonical labelings

• Not known
• Babai's paper does not address the question whether graphs permit quasipolynomial-time computable canonical forms
• McKay's algorithm is good for "average real life" graphs
• It is hard but possible to construct graphs with exponential running time
• It may be that the canonical labeling problem is harder that GI

Complexity of the Group Isomorphism Problem

• The strong connection between GI, group isomorphism and quasigroup isotopism is folklore
• Theorem (Robert Tarjan 1970s) Group Isomorphism is quasi-polynomial
• Hard cases: 2-step nilpotent -groups
• Recent developments by Xiaorui Sun (U Illinois at Chicago) link