On the automorphism groups of strongly regular graphs II

Babai, László (2015) On the automorphism groups of strongly regular graphs II. Journal of Algebra, 421. pp. 560-578. ISSN 0021-8693

Preview

Text 14itcs.pdf Download (299kB) | Preview

Abstract

We derive strong constraints on the automorphism groups of strongly regular (SR) graphs, resolving old problems motivated by Peter Cameron's 1981 description of large primitive groups.Trivial SR graphs are the disjoint unions of cliques of equal size and their complements. Graphic SR graphs are the line-graphs of cliques and of regular bipartite cliques (complete bipartite graphs with equal parts) and their complements.We conjecture that the order of the automorphism group of a non-trivial, non-graphic SR graph is quasi-polynomially bounded, i.e., it is at most exp<>((log<>n)C) for some constant C, where n is the number of vertices.While the conjecture remains open, we find surprisingly strong bounds on important parameters of the automorphism group. In particular, we show that the order of every automorphism is O(n8), and in fact O(n) if we exclude the line-graphs of certain geometries. We prove the conjecture for the case when the automorphism group is primitive; in this case we obtain a nearly tight n1+log2<>n bound.We obtain these bounds by bounding the fixicity of the automorphism group, i.e., the maximum number of fixed points of non-identity automorphisms, in terms of the second largest (in magnitude) eigenvalue and the maximum number of pairwise common neighbors of a regular graph. We connect the order of the automorphisms to the fixicity through an old lemma by Ákos Seress and the author.We propose to extend these investigations to primitive coherent configurations and offer problems and conjectures in this direction. Part of the motivation comes from the complexity of the Graph Isomorphism problem.

Actions (login required)

Edit Item