check
Special colloquium: Laci Babai (Chicago) "Graph isomorphism and coherent configurations: The Split-or-Johnson routine" | Einstein Institute of Mathematics

Special colloquium: Laci Babai (Chicago) "Graph isomorphism and coherent configurations: The Split-or-Johnson routine"

Date: 
Sun, 22/01/201716:00-18:00
Location: 
Rothberg B220 (CS bldg)
Coherent configurations" (CCs) are certain highly regular colorings of the directed complete graph. The concept goes back to Schur (1933) who used it to study permutation groups, and has subsequently been rediscovered in other contexts (block designs,
association schemes, graph canonization).
CCs are the central concept in the "Split-or-Johnson" (SoJ) procedure, one of the main combinatorial components of the speaker's recent algorithm to test graph isomorphism.
The talk will include the proof of a lemma about CCs that constitutes the "fix" of a gap recently found by Harald Helfgott in the SoJ procedure.
The talk is purely combinatorial, no group theory is requiered.