Johnson graph

Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J ( n , k ) {displaystyle J(n,k)} are the k {displaystyle k} -element subsets of an n {displaystyle n} -element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains ( k − 1 ) {displaystyle (k-1)} -elements. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson. Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J ( n , k ) {displaystyle J(n,k)} are the k {displaystyle k} -element subsets of an n {displaystyle n} -element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains ( k − 1 ) {displaystyle (k-1)} -elements. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson. There is a distance-transitive subgroup of A u t ( J ( n , k ) ) {displaystyle mathrm {Aut} (J(n,k))} isomorphic to S y m ( n ) {displaystyle mathrm {Sym} (n)} . In fact, A u t ( J ( n , k ) ) {displaystyle mathrm {Aut} (J(n,k))} ≅ S y m ( n ) {displaystyle mathrm {Sym} (n)} , unless n = 2 k ≥ 4 {displaystyle n=2kgeq 4} ; otherwise, A u t ( J ( n , k ) ) {displaystyle mathrm {Aut} (J(n,k))} ≅ S y m ( n ) × C 2 {displaystyle mathrm {Sym} (n) imes C_{2}} . As a consequence of being distance-transitive, J ( n , k ) {displaystyle J(n,k)} is also distance-regular. Letting d {displaystyle d} denote its diameter, the intersection array of J ( n , k ) {displaystyle J(n,k)} is given by { b 0 , ⋯ , b d − 1 ; c 1 , ⋯ c d } {displaystyle left{b_{0},cdots ,b_{d-1};c_{1},cdots c_{d} ight}} where: It turns out that unless J ( n , k ) {displaystyle J(n,k)} is J ( 8 , 2 ) {displaystyle J(8,2)} , its intersection array is not shared with any other distinct distance-regular graph; the intersection array of J ( 8 , 2 ) {displaystyle J(8,2)} is shared with three other distance-regular graphs that are not Johnson graphs. The Johnson graph J ( n , k ) {displaystyle J(n,k)} is closely related to the Johnson scheme, an association scheme in which each pair of k-element sets is associated with a number, half the size of the symmetric difference of the two sets. The Johnson graph has an edge for every pair of sets at distance one in the association scheme, and the distances in the association scheme are exactly the shortest path distances in the Johnson graph. The Johnson scheme is also related to another family of distance-transitive graphs, the odd graphs, whose vertices are k {displaystyle k} -element subsets of an ( 2 k + 1 ) {displaystyle (2k+1)} -element set and whose edges correspond to disjoint pairs of subsets. The vertex-expansion properties of Johnson graphs, as well as the structure of the corresponding extremal sets of vertices of a given size, are not fully understood. However, an asymptotically tight lower-bound on expansion of large sets of vertices was recently obtained. In general, determining the chromatic number of a Johnson graph is an open problem.