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

[img] Text
Restricted to Registered users only

Download (440kB) | Request a copy
Text (arXiv version)

Download (178kB) | Preview


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.

Item Type: Article
Uncontrolled Keywords: Distance-regular graphs; Delsarte clique; Clique geometry; Clique; Asymptotic analysis
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
Depositing User: MTMT SWORD
Date Deposited: 03 Jan 2017 13:46
Last Modified: 04 Jan 2017 08:27

Actions (login required)

View Item View Item