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
Abstract:
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.