Up

Johnson graphs

Selmer M. Johnson worked on bounds for codes, both unrestricted codes and constant weight codes. The Johnson scheme J(n,m) named after him is the association scheme of which the elements are the m-subsets of a n-set, and the relation (called Johnson distance) of two m-sets is half the size of their symmetric difference.

The Johnson graph J(n,m) is the graph that describes the distance-1 relation in the Johnson scheme. It is distance-regular of diameter min(m, n – m). In particular, for m = 2 it is strongly regular, and the parameters are v = m(m – 1)/2, k = 2(m – 2), λ = m – 2, μ = 4.

This graph J(n,2) is also known as the triangular graph T(n). It can be regarded as the special case of the block graph of a Steiner system for the trivial Steiner systems S(2,2,n). The first nontrivial case is T(5), the complement of the Petersen graph. For n smaller than 4 these graphs are complete. The graph T(4) is the complete multipartite graph K3×2, the complement of 3K2.

The triangular graphs T(n) are uniquely determined by their parameters when n is not 8. The three Chang graphs have the same parameters as T(8).

Kneser graph

The graph that describes being at maximum distance in the Johnson scheme is known as the Kneser graph. Thus, K(n,m) is the graph on the m-subsets of an n-set, adjacent when they are disjoint. When n = 2m+1 this graph is known as the Odd graph Om+1. Of course K(n,2) is the complement of the triangular graph T(n).

Independence and chromatic number

The triangular graph T(n) has independence number [n/2] and chromatic number n when n is odd, n–1 when n is even (so that the chromatic number is always odd).

The complement of the triangular graph T(n) has (for n at least 4) independence number n–1 and chromatic number n–2.

More generally, the Kneser graph K(n,m) has (for n at least 2m) independence number (n–1 choose m–1) and chromatic number n–2m+2.

The independence number of the Johnson graph J(n,m) is the size of the largest constant weight code with word length n, weight m, and minimum distance 4. There is a lot of literature. See, e.g., Brouwer et al. (1990). The chromatic number of J(n,m) is the minimum number of parts in a partition into such constant weight codes. One has χ(J(n,m)) ≤ n (since one can put the structure of abelian group on the coordinate positions, and all words with given sum of the elements in the support form a constant weight code with minimum distance 4). Often the chromatic number is a little bit smaller. For example, since there is for n = 1,3 (mod 6), n > 7, a partition of all triples into Steiner triple systems STS(n), it follows that χ(J(n,3)) = n–2 for these n. A general lower bound is χ(J(n,m)) ≥ n–m+1. See also Etzion & Bitan (1996) and Brouwer & Etzion (2009).

A table with bounds on the chromatic number of the Johnson graph J(n,m):

n\m 1234 5678
5 55
6 656
7 776
8 8776
9 9978
10 109108--9 8
11 11111010 8--9
12 12111110--11 10--118--9
13 13131111--13 10--1310--13
14 14131311--13 11--1410--1410--14
15 15151313--14 12--1511--1510--15
16 16151613--14 13--1512--1511--1610--15

References

A.E. Brouwer & T. Etzion, Some new distance-4 constant weight codes, Advances in Mathematics of Communications 5 (2011) 417-424.

A.E. Brouwer, James B. Shearer, N.J.A. Sloane & Warren D. Smith, A new table of constant weight codes, IEEE Trans. Inform. Th. 36 (1990) 1334-1380.

Tuvi Etzion & Sara Bitan, On the chromatic number, colorings, and codes of the Johnson graph, Discr. Applied Math. 70 (1996) 163-175.

Luc Teirlinck, A completion of Lu's determination of the spectrum of large sets of disjoint Steiner triple systems, J. Combin. Th. (A) 57 (1991) 302-305.

Lijun Ji, A new existence proof for large sets of disjoint Steiner triple systems, J. Combin. Th. (A) 112 (2005) 308-327.