Minicourse 1: The Cayley Isomorphism Problem
Syllabus: In 1967 Ádám conjectured that two circulant graphs Cay(
n, S) and Cay(n, T) are isomorphic if and only if there exists m ∈ n* such that mS = T. While this conjecture is not true (although from two different points of view it is mostly true), the conjecture was quickly generalized to ask for which groups G any two Cayley graphs Cay(G, S) and Cay(G, T) are isomorphic if and only if they are isomorphic by an automorphism of G (or α(S) = T for some automorphism α ∈ Aut(G)). Such a group G is a CI-group with respect to graphs. It is easy to show that α(Cay(G, T)) is a Cayley graph of G for every subset T of G and α ∈ Aut(G), so in testing isomorphism between two Cayley graphs of a group G one must always check to see if the automorphisms of G are isomorphisms. From this point of view, asking whether or not a group is a CI-group with respect to graphs is the same as asking if the minimal or necessary list of permutations that must be checked as possible isomorphisms is also a sufficient list of permutations to check. We will develop some of the main tools that are used to determine if a group is a CI-group with respect to graphs, along with appropriate permutation group theory. The groups G we will focus on will mainly be of small order (where small order means that there are not many prime factors). These groups are rich enough to illustrate some, but not all, of the proof techniques from permutation group theory and Schur ring theory that have been developed to show a group is a CI-group with respect to graphs as well as to highlight some of the obstacles for a group to be a CI-group with respect to graphs. We will also discuss how the techniques developed to attack the Cayley isomorphism problem can be modified to attack the isomorphism problem from graphs that are highly symmetric but not Cayley graphs nor even vertex-transitive, as well as to attack similar isomorphism problems for other classes of combinatorial objects.
Lecturers:
- Тed Dobson, Mississippi State University, USA, University of Primorska, Slovenia
- Istvan Kovacs, University of Primorska, Slovenia
