Babai, László and Wilmes, John (2016) Asymptotic Delsarte cliques in distanceregular graphs. Journal of Algebraic Combinatorics, 43 (4). pp. 771782. ISSN 09259899, ESSN: 15729192
Text
art3A10.10072Fs10801_015_0607_0_u.pdf Restricted to Registered users only Download (429Kb)  Request a copy 


Text (arXiv version)
1503.02746v1.pdf Download (174Kb)  Preview 
Abstract
We give a new bound on the parameter λ (number of common neighbors of a pair of adjacent vertices) in a distanceregular 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 distanceregular graphs with parameters satisfying kμ= o(λ2) are “asymptotically Delsartegeometric.” © 2015, Springer Science+Business Media New York.
Item Type:  Article 

Uncontrolled Keywords:  Distanceregular graphs; Delsarte clique; Clique geometry; Clique; Asymptotic analysis 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  03 Jan 2017 13:46 
Last Modified:  04 Jan 2017 08:27 
URI:  http://real.mtak.hu/id/eprint/44381 
Actions (login required)
View Item 