A local characterization of the Johnson scheme

DOI10.1007/BF02579203MaRDI QIDQ1107538zbMATH OpenOpenAlexFDO

Authors J. I. Hall

Publication date 1987

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02579203

zbMATH Keywords

association schemedistance regular graphsJohnson scheme

Mathematics Subject Classification ID

Designs and configurations (05B99) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 966482
• Subschemes of the Johnson scheme
• scientific article; zbMATH DE number 6602525
• A localized Jarník-Besicovitch theorem
• scientific article; zbMATH DE number 4203713
• Local algorithms on yablonskii schemes
• scientific article; zbMATH DE number 3562507
• The first distribution invariant of the Johnson-scheme
• MMS-type problems for Johnson scheme
• scientific article; zbMATH DE number 4181608

Cites work

• Characerization of a class of distance regular graphs.
• scientific article; zbMATH DE number 3884178 (Why is no real title available?)
• scientific article; zbMATH DE number 3672329 (Why is no real title available?)
• Locally 4‐by‐4 grid graphs
• Locally cotriangular graphs
• Locally polar spaces and related rank 3 groups
• On Identifying PG(3,2) and the Complete 3-Design on Seven Points
• The graphs G(n,k) of the Johnson schemes are unique for n\(\geq 20\)

Cited in

(15)

• Bounding the diameter of a distance regular graph by a function of \(k_ d\)
• Subschemes of the Johnson scheme
• Locally \(K_{3,3}\) or Petersen graphs
• Covering spaces of locally homogeneous graphs
• Covering projections of graphs preserving links of vertices and edges
• Distance-preserving subgraphs of Johnson graphs
• A characterization of Grassmann and Johnson graphs
• The 2-partially distance-regular graphs such that their second largest local eigenvalues are at most one
• Graphs which are edge-locally C_n
• An infinite family of incidence geometries whose incidence graphs are locally \(X^\ast\)
• The local recognition of reflection graphs of spherical Coxeter groups
• Some locally Kneser graphs
• Local recognition of the point graphs of some Lie incidence geometries
• The first distribution invariant of the Johnson-scheme
• The graphs G(n,k) of the Johnson schemes are unique for n\(\geq 20\)

This page was built for publication: A local characterization of the Johnson scheme

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107538)