19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

The Cayley Isomorphism (CI) Problem

Presented by Joy MORRIS
Type: Oral presentation
Track: Cayley Graphs

Content

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=\rm{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.

Place

Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

More

Co-authors

More