Johnson graph

Johnson graph
The Johnson graph J(5,2)
Named after	Selmer M. Johnson
Vertices	$\binom{n}{k}$
Edges	$\frac{k (n - k)}{2} \binom{n}{k}$
Diameter	$\min(k,n-k)$
Properties	$(k(n-k))$-regular Vertex-transitive Distance-transitive Hamilton-connected
Notation	$J(n,k)$

Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph $J(n,k)$ are the $k$-element subsets of an $n$-element set; two vertices are adjacent when they meet in a $(k-1)$-element set.^[1] Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.

Special cases

• $J(n,1)$ is the complete graph K_n.
• $J(4,2)$ is the octahedral graph.
• $J(5,2)$ is the complement graph of the Petersen graph,^[1] hence the line graph of K₅. More generally, for all n, the Johnson graph $J(n,2)$ is the complement of the Kneser graph $KG(n,2)$

Properties

In the Johnson graph, the distance between every two vertices is half of the Hamming distance between the sets corresponding to the vertices. Johnson graphs are distance-transitive graphs: there is a graph automorphism mapping any pair of vertices to any other pair at the same distance.^[2]

As a consequence of being distance-transitive, every Johnson graph is also distance-regular. This means that, for every possible distance $d$ between two vertices in the graph, there is a triple of numbers $(a_d,b_d,c_d)$ such that, for every pair $(v,w)$ of vertices at distance $d$ from each other, $w$ has exactly $a_i$ neighbors at distance $d$ from $v$, exactly $b_i$ neighbors at distance $d+1$ from $v$, and exactly $c_i$ neighbors at distance $d-1$ from $v$. These triples of numbers can be grouped into a matrix with one column per distance, called the intersection array of the graph, and this intersection array may be used to classify the distance-transitive graphs. It turns out that the intersection arrays of Johnson graphs are almost always enough to classify them completely: except for $J(8,2)$, each Johnson graph has an intersection array that is not shared with any other graph. However, the intersection array of $J(8,2)$ is shared with three other distance-regular graphs that are not Johnson graphs.^[1]

Every Johnson graph is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a Hamiltonian path in the graph. In particular this means that it has a Hamiltonian cycle.^[3] Every Johnson graph J(n,k) forms the graph of vertices and edges of an (n − 1)-dimensional polytope, called a hypersimplex.^[4]

The eigenvectors of Johnson graph have an explicit description.^[5]

The vertex-expansion properties of Johnson graph, 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.^[6] It is also known that the Johnson graph $J(n,k)~$ is $~k(n-k)$-vertex-connected.^[7]

Relation to Johnson scheme

The Johnson graph $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.^[2] 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.^[8]

The Johnson scheme is also related to another family of distance-transitive graphs, the odd graphs, whose vertices are $k$-element subsets of an $(2k+1)$-element set and whose edges correspond to disjoint pairs of subsets.^[2]

References

1. Holton, D. A.; Sheehan, J. (1993), "The Johnson graphs and even graphs", The Petersen graph, Australian Mathematical Society Lecture Series 7, Cambridge: Cambridge University Press, p. 300, doi:10.1017/CBO9780511662058, ISBN 0-521-43594-3, MR 1232658.
2. Cameron, Peter J. (1999), Permutation Groups, London Mathematical Society Student Texts 45, Cambridge University Press, p. 95, ISBN 9780521653787.
3. Alspach, Brian (2013), "Johnson graphs are Hamilton-connected", Ars Mathematica Contemporanea 6 (1): 21–23.
4. Rispoli, Fred J. (2008), The graph of the hypersimplex, arXiv:0811.2981.
5. Filmus, Yuval (2014), Orthogonal basis for functions over a slice of the Boolean hypercube, arXiv:1406.0142.
6. Christofides, Demetres; Ellis, David; Keevash, Peter (2013), "An Approximate Vertex-Isoperimetric Inequality for $r$-sets", The Electronic Journal of Combinatorics 4 (20).
7. Newman, Ilan; Rabinovich, Yuri (2015), On Connectivity of the Facet Graphs of Simplicial Complexes, arXiv:1502.02232.
8. The explicit identification of graphs with association schemes, in this way, can be seen in Bose, R. C. (1963), "Strongly regular graphs, partial geometries and partially balanced designs", Pacific Journal of Mathematics 13: 389–419, doi:10.2140/pjm.1963.13.389, MR 0157909.

External links

• Weisstein, Eric W., "Johnson Graph", MathWorld.
• Brouwer, Andries E. "Johnson graphs".