BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

The Sun--Wilmes classification of primitive coherent configurations with many automorphisms Kivva, Bohdan


This talk is based on the paper by Xiaorui Sun and John Wilmes, "Structure and automorphisms of primitive coherent configurations", arXiv:1510.02195 (2015). Coherent configurations (CCs) are edge-colorings of the complete directed graph satisfying certain regularity conditions, modeling the orbitals (orbits on ordered pairs) of permutation groups. Introduced by Schur in 1934 for the study of permutation groups, CCs also include strongly regular graphs and association schemes, structures that do not necessarily arise from groups. Primitive CCs (PCCs) are a combinatorial model of primitive permutation groups. A base of a permutation group is a subset of the permutation domain of which the pointwise stabilizer is the identity. A base of a structure (such as a graph or a CC) is a base of its automorphism group. The minimum size of a base is a measure of the cost of destroying all symmetry. 37 years ago Babai gave a nearly tight $O(\sqrt{n}\log n)$ upper bound on the minimum base size of PCCs with the trivial exception of the clique (Annals of Math, 1981). As a corollary, this result solved the then century-old problem of bounding the order of primitive permutation groups in an unexpected, purely combinatorial way. In a major recent development, Sun and Wilmes reduced the upper bound to $O(n^{1/3}(\log n)^{4/3})$, with known exceptions. As a corollary, they classify the largest primitive permutation groups, a result previously only known through the classification of finite simple groups (CFSG) (Cameron 1981). At the same time, the scope of their result goes significantly beyond primitive permutation groups, into a combinatorial domain where the CFSG has little relevance. To prove their result, Sun and Wilmes develop a combinatorial structure theory of PCCs. A crucial element of their theory is the discovery of "asymptotically uniform clique geometries" in PCCs with parameters in a certain range. Like Babai's, the Sun-Wilmes result is algorithmic: the proof is an analysis of the individualization/refinement method.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International