Description:
We develop new structure theory for highly regular combinatorial objects,
including Steiner designs, strongly regular graphs, and coherent
configurations. As applications, we make progress on old problems in algebraic
combinatorics and the theory of permutation groups, and break decades-old
barriers on the complexity of the algorithmic Graph Isomorphism problem.
A central aspect of our structural contributions is the discovery of clique
geometries in regular structures. A second aspect is bounds on the
rate of expansion of small sets.
In the case of Steiner designs, we give a $n^{O(\log n)}$ bound on the number
of automorphisms where $n$ is the number of points. This result is nearly
optimal in two ways: it essentially matches the number of automorphisms in
affine or projective space, and we show that the bound does not extend to the
broader class of balanced incomplete block designs. The line-graphs of Steiner
designs are strongly regular graphs, and in fact are one of the cases of
Neumaier's classification of strongly regular graphs. We bound the number of
reconstructions of a Steiner design from its line-graph in order to apply our
automorphism bound for Steiner designs to this class of strongly regular
graphs, and show that this class of strongly regular graphs has at most
$\exp(\tilde{O}(v^{1/14}))$ automorphisms, where $v$ is the number of vertices and
the $\tilde{O}$ hides polylogarithmic factors.
We give an $\exp(\tilde{O}(1 + \lambda/\mu))$ bound on the number of
automorphisms of any nontrivial $\SR(v,\rho,\lambda,\mu)$ strongly regular
graph. (Here, $v$ is the number of vertices, $\rho$ is the valency, and
$\lambda$ and $\mu$ are the number of common neighbors of a pair of adjacent
and nonadjacent vertices, respectively.) As a consequence, we obtain a
quasipolynomial bound on the number of automorphisms when $\rho =
\Omega(v^{5/6})$.
In further study of the structure of the automorphism groups of
$\SR(v,\rho,\lambda,\mu)$ graphs, we find a $\Gamma_\mu$ subgroup of index
$v^{O(\log v)}$ (i.e., a subgroup of index $v^{O(\log v)}$ for which all
composition factors are subgroups of $S_{\mu}$) with known exceptions. In
combination with our bound on the number of automorphisms and an earlier bound
due to Spielman, we find a $\Gamma_d$ subgroup of the automorphism group of
index $v^d$, where $d = \tilde{O}(v^{1/5})$, again with known exceptions.
We classify the primitive coherent configurations with not less than
$\exp(\tilde{O}(v^{1/3}))$ automorphisms, where $v$ is the number of vertices. As a
corollary to our combinatorial classification result, we infer a classification
of large primitive permutation groups, previously known only through the
Classification of Finite Simple Groups.
As a consequence of the combinatorial structure underlying our bounds for the
automorphism groups, we give corresponding bounds for the time-complexity of
deciding isomorphism. When we bound the order of the automorphism group, our
time-complexity bounds are identical to the bounds on the order. From our study
of the composition factors of automorphism groups of strongly regular graphs,
we obtain a $v^{\mu + O(\log v)}$ and a $\exp(\tilde{O}(v^{1/5}))$ bound on the
time-complexity of deciding isomorphism of strongly regular graphs.