Combinatorics Seminar
Speaker: L. Babai, University of Chicago
Title: Hidden irregularity versus robust symmetry: Coherent configurations and the Graph Isomorphism problem
Abstract
The Split-or-Johnson (SoJ) routine finds hidden robust symmetry in the form of a canonically embedded large Johnson graph in objects lacking significant hidden irregularity.
Of interest in its own right in the “structure versus irregularity” context, SoJ was designed as a combinatorial partitioning tool to expand the reach of Luks’s group-theoretic divide-and-conquer strategy to the general Graph Isomorphism problem.
We shall give a complete proof of the fix of the gap found recently by Harald Helfgott in an earlier version of the SoJ routine. The central concept in our discussion is “coherent configurations,” highly regular edge-colorings of the complete directed graph, first introduced by Schur (1933) and subsequently rediscovered in several different contexts.
Attendance of the speaker’s lecture the previous day (Wednesday) will not be assumed. The talk will be purely combinatorial, no group theory will be required.