Combinatorics Seminar - L. Babai, University of Chicago

Event time: 
Thursday, February 16, 2017 - 4:00pm
215 LOM See map
12 Hillhouse Avenue
New Haven, CT 06511
Event description: 

Combinatorics Seminar

Speaker: L. Babai, University of Chicago

Title: Hidden irregularity versus robust symmetry: Coherent configurations and the Graph Isomorphism problem


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.