On the spectral gap and the automorphism group of distance-regular graphs

DOI10.1016/J.JCTB.2021.02.003arXiv1912.10571MaRDI QIDQ6331634

Bohdan Kivva

Publication date: 22 December 2019

Abstract: We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. We use the spectral gap bound to study the structure of the automorphism group. The minimal degree of a permutation group $G$ is the minimum number of points not fixed by non-identity elements of $G$. Lower bounds on the minimal degree have strong structural consequences on $G$. In 2014 Babai proved that the automorphism group of a strongly regular graph with $n$ vertices has minimal degree $geqcn$, with known exceptions. Strongly regular graphs correspond to distance-regular graphs of diameter 2. Babai conjectured that Hamming and Johnson graphs are the only primitive distance-regular graphs of diameter $dgeq3$ whose automorphism group has sublinear minimal degree. We confirm this conjecture for non-geometric primitive distance-regular graphs of bounded diameter. We also show if the primitivity assumption is removed, then only one additional family of exceptions arises, the cocktail-party graphs. We settle the geometric case in a companion paper.

Mathematics Subject Classification ID

Designs and configurations (05Bxx) Abstract finite groups (20Dxx) Permutation groups (20Bxx)

This page was built for publication: On the spectral gap and the automorphism group of distance-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6331634)