SEMINAR: Groups and Combinatorics Seminar: The Cayley Isomorphism (CI) problem

Groups and Combinatorics Seminar

Joy Morris (University of Lethbridge, Canada)

will speak on

The Cayley Isomorphism (CI) problem

at 12 noon in MLR2 on Tuesday 8th of March

Abstract: In a perfect world in which all isomorphisms between graphs must be in some sense ``natural," it would be possible to attack the problem of determining whether or not given graphs are isomorphic, simply by checking a (hopefully small) class of ``natural" isomorphisms. For Cayley graphs, ``natural" isomorphisms between the graphs Cay(G;S) and Cay(G;S') on the group G, would consist exclusively of automorphisms of the group G. Alas, our world is not perfect. However, there are some Cayley graphs X=Cay(G;S) for which the isomorphism problem can be solved in this manner. That is, for such a graph X, the Cayley graph Cay(G;S') is isomorphic to X if and only if there is an automorphism of G that takes S to S' (and hence acts as a graph isomorphism). Such a graph is said to have the Cayley Isomorphism, or CI, property. Furthermore, there are some groups G for which every Cayley graph Cay(G;S) has the CI property; these groups are said to have the CI property. The Cayley Isomorphism problem is the problem of determining which graphs, and which groups, have the CI property.

In this talk, I will discuss the motivation and background of the CI problem (which stems from a 1977 paper by Laszlo Babai), and survey some of the results that have been obtained on this problem. Traditionally, the problem has been confined to finite Cayley graphs. Towards the end of the talk, I will discuss the extension of this problem to infinite graphs, and some results I have obtained on locally finite graphs in joint work with Babai.

All welcome