Johnson graph (original) (raw)

From Wikipedia, the free encyclopedia

Class of undirected graphs defined from systems of sets

Johnson graph
The Johnson graph J(5,2)
Named after	Selmer M. Johnson
Vertices	( n k ) {\displaystyle {\binom {n}{k}}} ${\binom {n}{k}}$
Edges	1 2 k ( n − k ) ( n k ) {\displaystyle {\frac {1}{2}}k(n-k){\binom {n}{k}}} ${\frac {1}{2}}k(n-k){\binom {n}{k}}$
Diameter	min ( k , n − k ) {\displaystyle \min(k,n-k)} $\min(k,n-k)$
Properties	k ( n − k ) {\displaystyle k(n-k)} $k(n-k)$ -regular Vertex-transitive Distance-transitive Hamilton-connected Polytopal
Notation	J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$
Table of graphs and parameters

In mathematics, 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)} $J(n,k)$ are the k {\displaystyle k} $k$ -element subsets of an n {\displaystyle n} $n$ -element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains ( k − 1 ) {\displaystyle (k-1)} $(k-1)$ -elements.[1] Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson.

Both J ( n , 1 ) {\displaystyle J(n,1)} $J(n,1)$ and J ( n , n − 1 ) {\displaystyle J(n,n-1)} $J(n,n-1)$ are the complete graph Kn.
J ( 4 , 2 ) {\displaystyle J(4,2)} $J(4,2)$ is the octahedral graph.[2]
J ( 5 , 2 ) {\displaystyle J(5,2)} $J(5,2)$ is the complement of the Petersen graph,[1] hence the line graph of _K_5. More generally, for all n {\displaystyle n} $n$ , the Johnson graph J ( n , 2 ) {\displaystyle J(n,2)} $J(n,2)$ is the line graph of Kn and the complement of the Kneser graph K ( n , 2 ) . {\displaystyle K(n,2).} $K(n,2).$

Graph-theoretic properties

[edit]

J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is isomorphic to J ( n , n − k ) . {\displaystyle J(n,n-k).} $J(n,n-k).$
For all 0 ≤ j ≤ diam ⁡ ( J ( n , k ) ) {\displaystyle 0\leq j\leq \operatorname {diam} (J(n,k))} $0\leq j\leq \operatorname {diam} (J(n,k))$ , any pair of vertices at distance j {\displaystyle j} $j$ share k − j {\displaystyle k-j} $k-j$ elements in common.
J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ 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]
It is also known that the Johnson graph J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is k ( n − k ) {\displaystyle k(n-k)} $k(n-k)$ -vertex-connected.[4]
J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ forms the vertex-edge graph of an (n − 1)-dimensional polytope, called a hypersimplex.[5]
Any maximal clique is either of the form { S ∪ { x } ∣ x ∈ { 1 , … , n } ∖ S } {\displaystyle \{S\cup \{x\}\mid x\in \{1,\dots ,n\}\setminus S\}} $\{S\cup \{x\}\mid x\in \{1,\dots ,n\}\setminus S\}$ for a ( k − 1 ) {\displaystyle (k-1)} $(k-1)$ -element subset S {\displaystyle S} $S$ and k < n − 1 {\displaystyle k<n-1} $k<n-1$ , or of the form { S ∖ { x } ∣ x ∈ S } {\displaystyle \{S\setminus \{x\}\mid x\in S\}} $\{S\setminus \{x\}\mid x\in S\}$ for a ( k + 1 ) {\displaystyle (k+1)} $(k+1)$ -element set S {\displaystyle S} $S$ for k > 1 {\displaystyle k>1} $k>1$ , or of the form { { 1 } , { 2 } } {\displaystyle \{\{1\},\{2\}\}} $\{\{1\},\{2\}\}$ in the edge case ( n , k ) = ( 2 , 1 ) {\displaystyle (n,k)=(2,1)} $(n,k)=(2,1)$ .[6]
The clique number of J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is given by an expression in terms of its least and greatest eigenvalues: ω ( J ( n , k ) ) = 1 − λ max / λ min {\displaystyle \omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }} $\omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }$ , or, by the above explicit description of maximal cliques, ω ( J ( n , k ) ) = max { k + 1 , N − k + 1 } . {\displaystyle \omega (J(n,k))=\max\{k+1,N-k+1\}.} $\omega (J(n,k))=\max\{k+1,N-k+1\}.$
The clique cover number of J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ satisfies θ ( J ( n , 1 ) ) = 1 {\displaystyle \theta (J(n,1))=1} $\theta (J(n,1))=1$ for n > 1 {\displaystyle n>1} $n>1$ , θ ( J ( n , 2 ) ) = n − 2 {\displaystyle \theta (J(n,2))=n-2} $\theta (J(n,2))=n-2$ for n > 2 {\displaystyle n>2} $n>2$ and θ ( J ( n , 3 ) ) = ⌊ ( n − 1 ) 2 / 4 ⌋ {\displaystyle \theta (J(n,3))=\lfloor (n-1)^{2}/4\rfloor } $\theta (J(n,3))=\lfloor (n-1)^{2}/4\rfloor$ for n > 5 {\displaystyle n>5} $n>5$ but is not known in general.[7]
The chromatic number of J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is at most n , χ ( J ( n , k ) ) ≤ n . {\displaystyle n,\chi (J(n,k))\leq n.} $n,\chi (J(n,k))\leq n.$ [8]
Each Johnson graph is locally grid, meaning that the induced subgraph of the neighbors of any vertex is a rook's graph. More precisely, in the Johnson graph J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ , each neighborhood is a k × ( n − k ) {\displaystyle k\times (n-k)} $k\times (n-k)$ rook's graph.[9]

There is a distance-transitive subgroup of Aut ⁡ ( J ( n , k ) ) {\displaystyle \operatorname {Aut} (J(n,k))} $\operatorname {Aut} (J(n,k))$ isomorphic to Sym ⁡ ( n ) {\displaystyle \operatorname {Sym} (n)} $\operatorname {Sym} (n)$ . In fact, Aut ⁡ ( J ( n , k ) ) ≅ Sym ⁡ ( n ) {\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)} $\operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)$ , except that when n = 2 k ≥ 4 {\displaystyle n=2k\geq 4} $n=2k\geq 4$ , Aut ⁡ ( J ( n , k ) ) ≅ Sym ⁡ ( n ) × C 2 {\displaystyle \operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}} $\operatorname {Aut} (J(n,k))\cong \operatorname {Sym} (n)\times C_{2}$ .[10]

As a consequence of being distance-transitive, J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is also distance-regular. Letting d {\displaystyle d} $d$ denote its diameter, the intersection array of J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is given by

{ b 0 , … , b d − 1 , c 1 , … c d } {\displaystyle \left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}} $\left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}$

where:

b j = ( k − j ) ( n − k − j ) 0 ≤ j < d c j = j 2 0 < j ≤ d {\displaystyle {\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}} ${\begin{aligned}b_{j}&=(k-j)(n-k-j)&&0\leq j<d\\c_{j}&=j^{2}&&0<j\leq d\end{aligned}}$

It turns out that unless J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is J ( 8 , 2 ) {\displaystyle J(8,2)} $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)} $J(8,2)$ is shared with three other distance-regular graphs that are not Johnson graphs.[1]

Eigenvalues and eigenvectors

[edit]

The characteristic polynomial of J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ is given by

ϕ ( x ) := ∏ j = 0 diam ⁡ ( J ( n , k ) ) ( x − A n , k ( j ) ) ( n j ) − ( n j − 1 ) . {\displaystyle \phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right)^{{\binom {n}{j}}-{\binom {n}{j-1}}}.} $\phi (x):=\prod _{j=0}^{\operatorname {diam} (J(n,k))}\left(x-A_{n,k}(j)\right)^{{\binom {n}{j}}-{\binom {n}{j-1}}}.$

where A n , k ( j ) = ( k − j ) ( n − k − j ) − j . {\displaystyle A_{n,k}(j)=(k-j)(n-k-j)-j.} $A_{n,k}(j)=(k-j)(n-k-j)-j.$ [10]

The eigenvectors of J ( n , k ) {\displaystyle J(n,k)} $J(n,k)$ have an explicit description.[11]

The Johnson graph J ( n , k ) {\displaystyle J(n,k)} $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.[12] 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.[13]

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

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.[14]

In general, determining the chromatic number of a Johnson graph is an open problem.[15]

Grassmann graph

^ a b c Holton, D. A.; Sheehan, J. (1993), "The Johnson graphs and even graphs", The Petersen graph, Australian Mathematical Society Lecture Series, vol. 7, Cambridge: Cambridge University Press, p. 300, doi:10.1017/CBO9780511662058, ISBN 0-521-43594-3, MR 1232658.
^ Stanić, Zoran (2017), Regular Graphs: A Spectral Approach, de Gruyter, p. 63–64, ISBN 978-3-11-035135-4
^ Alspach, Brian (2013), "Johnson graphs are Hamilton-connected", Ars Mathematica Contemporanea, 6 (1): 21–23, doi:10.26493/1855-3974.291.574.
^ Newman, Ilan; Rabinovich, Yuri (2015), On Connectivity of the Facet Graphs of Simplicial Complexes, arXiv:1502.02232, Bibcode:2015arXiv150202232N.
^ Rispoli, Fred J. (2008), The graph of the hypersimplex, arXiv:0811.2981, Bibcode:2008arXiv0811.2981R.
^ Ramras, Mark; Donovan, Elizabeth (2011), "The automorphism group of a Johnson graph", SIAM Journal on Discrete Mathematics, 25 (1): 267–270, doi:10.1137/090765596
^ Jørgensen, Søren F. (2025), "On the clique covering numbers of Johnson graphs", Designs, Codes and Cryptography, 93 (9): 3689–3705, arXiv:2502.15019, doi:10.1007/s10623-025-01663-3
^ "Johnson", www.win.tue.nl, retrieved 2017-07-26
^ Cohen, Arjeh M. (1990), "Local recognition of graphs, buildings, and related geometries" (PDF), in Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.), Finite Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries held in Pingree Park, Colorado, July 17–23, 1988, Oxford Science Publications, Oxford University Press, pp. 85–94, MR 1072157; see in particular pp. 89–90
^ a b Brouwer, Andries E. (1989), Distance-Regular Graphs, Cohen, Arjeh M., Neumaier, Arnold., Berlin, Heidelberg: Springer Berlin Heidelberg, ISBN 9783642743436, OCLC 851840609
^ Filmus, Yuval (2014), "An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube", The Electronic Journal of Combinatorics, 23 P1.23, arXiv:1406.0142, Bibcode:2014arXiv1406.0142F, doi:10.37236/4567, S2CID 7416206.
^ a b Cameron, Peter J. (1999), Permutation Groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, p. 95, ISBN 9780521653787.
^ 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 (2): 389–419, doi:10.2140/pjm.1963.13.389, MR 0157909.
^ Christofides, Demetres; Ellis, David; Keevash, Peter (2013), "An Approximate Vertex-Isoperimetric Inequality for rrr-sets", The Electronic Journal of Combinatorics, 4 (20).
^ Godsil, C. D.; Meagher, Karen (2016), Erdős-Ko-Rado theorems : algebraic approaches, Cambridge, United Kingdom, ISBN 9781107128446, OCLC 935456305{{[citation](/wiki/Template:Citation "Template:Citation")}}: CS1 maint: location missing publisher (link)