[Colloquium] Combinatorics & Theoretical CS Seminar

[Donna Brooms]

REMINDER:

Combinatorics & Theoretical Computer Science Seminar


John Wilmes
University of Chicago (Math)
www.math.uchicago.edu

Tuesday, October 6, 2015
Ryerson 251 @ 3:00 pm

Title: “Structure and automorphisms of primitive coherent configurations”

Abstract: Primitive coherent configurations (PCCs) are colorings of the complete directed graph with strong regularity constraints, generalizing strongly regular graphs.


We prove that PCCs have at most f(n)=exp(O~(n^{1/3})) automorphisms, with known exceptions.  This is the first improvement over Babai's 1981 bound of g(n)=exp(O~(n^{1/2})).  A corollary to this purely combinatorial result characterizes primitive permutation groups of order greater than f(n), a result previously only known through the classification of finite simple groups (Cameron 1981).  Another corollary of the underlying result is that canonical forms for PCCs can be found in time f(n), again the first improvement over Babai’s 1981 bound of g(n).

For the proof we develop a structure theory of PCCs.  In particular, we find that PCCs have an interesting clique geometry in a certain range of the parameters.


Joint work with Xiaorui Sun, presented at STOC 2015.

Host: Prof. Laszlo Babai
(Refreshments will be served prior to the talk in Ry. 255 @ 2:30)



-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20151006/97b5d143/attachment.htm