Asymptotic Delsarte cliques in distance-regular graphs

Babai, László and Wilmes, John (2016) Asymptotic Delsarte cliques in distance-regular graphs. Journal of Algebraic Combinatorics, 43 (4). pp. 771-782. ISSN 0925-9899, ESSN: 1572-9192

	Text art3A10.10072Fs10801_015_0607_0_u.pdf Restricted to Registered users only Download (440kB) | Request a copy
Preview	Text (arXiv version) 1503.02746v1.pdf Download (178kB) | Preview

Abstract

We give a new bound on the parameter λ (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 Spielman (1996) and Pyber (2014. arXiv:1409.3041). The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs (Babai et al. 2013). The proof is based on a clique geometry found by Metsch (Des Codes Cryptogr 1(2):99–116, 1991) under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch’s result: If kμ= o(λ2) , then each edge of G belongs to a unique maximal clique of size asymptotically equal to λ, and all other cliques have size o(λ). Here k denotes the degree and μ 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μ= o(λ2) , so families of distance-regular graphs with parameters satisfying kμ= o(λ2) are “asymptotically Delsarte-geometric.” © 2015, Springer Science+Business Media New York.

Actions (login required)

Edit Item