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

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.


Sun, 22/01/2017 - 16:00 to 18:00


Rothberg B220 (CS bldg)