A local characterization of the Johnson scheme (Q1107538)

The Johnson scheme \({\mathcal J}(m,d)\) is the association scheme of all d- subsets of an m-set, the pair (x,y) of d-subsets in relation \({\mathcal J}_ i\), \(0\leq i\leq d\), provided \(| x\cap y| =d-i\). In this paper, within the Johnson scheme \({\mathcal J}(m,d)\) the graph K(m,d) of d-subsets of an m-set, two such adjacent when disjoint, is found. Among all connected graphs, K(m,d) is characterized by the isomorphism type of its vertex neighborhoods provided m is sufficiently large compared to d. The theorems find applications in the characterization of the Johnson scheme among the primitive association schemes and distance regular graphs.