Combinatorics Seminar

When: Sunday, January 22, 10am
Where: Schreiber 309
Speaker: László Babai, University of Chicago
Title: Canonical partitioning and the emergence of the Johnson graphs: Combinatorial aspects of the Graph Isomorphism problem


We shall discuss combinatorial aspects of the speaker's recent quasipolynomial-time algorithm for the Graph Isomorphism problem. After a group theoretic initialization phase, the algorithm employs a combinatorial divide-and-conquer strategy. The Johnson graphs turn out to be the sole obstructions to efficient partitioning.

Attendance of the speaker's lecture the preceding Wednesday will not be assumed.