Asymptotic Delsarte cliques in distance-regular graphs

Babai, László ; Wilmes, John

Journal of Algebraic Combinatorics, Tome 43 (2016) no. 4, pp. 771-782.

Résumé

We give a new bound on the parameter $\lambda $ (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph $G$, improving and generalizing bounds for strongly regular graphs by D. A. Spielman [in: Proceedings of the 28th annual ACM symposium on the theory of computing (STOC). Philadelphia, PA, USA, May 22--24, 1996. New York, NY: ACM, 576--584 (1996; Zbl 0915.05104)] and L. Pyber ["Large connected strongly regular graphs are Hamiltonian", Preprint, arXiv:1409.3041]. The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs. The proof is based on a clique geometry found by K. Metsch [Des. Codes Cryptography 1, No. 2, 99--116 (1991; Zbl 0760.05012)] under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch's result: If $k\mu = o(\lambda ^2)$, then each edge of $G$ belongs to a unique maximal clique of size asymptotically equal to $\lambda $, and all other cliques have size $o(\lambda )$. Here $k$ denotes the degree and $\mu $ the number of common neighbors of a pair of vertices at distance 2. We point out that Metsch's cliques are "asymptotically Delsarte" when $k\mu = o(\lambda ^2)$, so families of distance-regular graphs with parameters satisfying $k\mu = o(\lambda ^2)$ are "asymptotically Delsarte-geometric."

Détail

Classification : 05C12, 05E30, 05C69
Keywords: distance-regular graphs, clique, clique geometry, Delsarte clique, asymptotic analysis