One of the fundamental computational problems in the complexity
class NP on Karp's 1973 list, the Graph Isomorphism problem asks
to decide whether or not two given graphs are isomorphic. While
program packages exist that solve this problem remarkably
efficiently in practice (McKay, Piperno, and others), for
complexity theorists the problem has been notorious for its
unresolved asymptotic worst-case complexity.
In this talk we outline a key combinatorial ingredient of the
speaker's recent algorithm for the problem.
A divide-and-conquer approach requires efficient canonical
partitioning of graphs and higher-order relational structures.
We shall indicate why Johnson graphs are the sole obstructions
to this approach.
This talk will be purely combinatorial, no familiarity
with group theory will be required.