Johnson graph

Johnson graph
Johnson graph
	The Johnson graph J(5,2)
Named after	Selmer M. Johnson
Vertices
Edges
Diameter
Properties	-regular ; Vertex-transitive ; Distance-transitive ; Hamilton-connected
Notation
	Table of graphs and parameters

Last updated August 15, 2024

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

Special cases

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

Graph-theoretic properties

$J(n,k)$ is isomorphic to $J(n,n-k).$
For all $0\leq j\leq \operatorname {diam} (J(n,k))$ , any pair of vertices at distance $j$ share $k-j$ elements in common.
$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.^[2]
It is also known that the Johnson graph $J(n,k)$ is $k(n-k)$ -vertex-connected.^[3]
$J(n,k)$ forms the graph of vertices and edges of an (n − 1)-dimensional polytope, called a hypersimplex.^[4]
the clique number of $J(n,k)$ is given by an expression in terms of its least and greatest eigenvalues: $\omega (J(n,k))=1-\lambda _{\max }/\lambda _{\min }.$
The chromatic number of $J(n,k)$ is at most $n,\chi (J(n,k))\leq n.$ ^[5]
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)$ , each neighborhood is a $k\times (n-k)$ rook's graph.^[6]

Automorphism group

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

Intersection array

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

\left\{b_{0},\ldots ,b_{d-1},c_{1},\ldots c_{d}\right\}

where:

{\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)$ is $J(8,2)$ , its intersection array is not shared with any other distinct distance-regular graph; the intersection array of $J(8,2)$ is shared with three other distance-regular graphs that are not Johnson graphs.^[1]

Eigenvalues and eigenvectors

The characteristic polynomial of $J(n,k)$ is given by

\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.

^[7]

The eigenvectors of $J(n,k)$ have an explicit description.^[8]

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.^[9] 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.^[10]

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.^[9]

Open problems

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.^[11]

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

Related Research Articles

In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say, blue and red), let $r$ and $s$ be any two positive integers. Ramsey's theorem states that there exists a least positive integer $R (r, s)$ for which every blue-red edge colouring of the complete graph on $R (r, s)$ vertices contains a blue clique on $r$ vertices or a red clique on $s$ vertices. (Here $R (r, s)$ signifies an integer that depends on both $r$ and $s$ .)

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

<span class="mw-page-title-main">Hypergraph</span> Generalization of graph theory

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.

In mathematics, the isoperimetric inequality is a geometric inequality involving the perimeter of a set and its volume. In $-dimensional space the inequality lower bounds the surface area or perimeter of a set by its volume,$

<span class="mw-page-title-main">Tournament (graph theory)</span> Directed graph where each vertex pair has one arc

In graph theory, a tournament is a directed graph with exactly one edge between each two vertices, in one of the two possible directions. Equivalently, a tournament is an orientation of an undirected complete graph. The name tournament comes from interpreting the graph as the outcome of a round-robin tournament, a game where each player is paired against every other exactly once. In a tournament, the vertices represent the players, and the edges between players point from the winner to the loser.

<span class="mw-page-title-main">Desargues graph</span> Distance-transitive cubic graph with 20 nodes and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

In graph theory, the Kneser graph $K (n, k)$ (alternatively $KG n, k$ ) is the graph whose vertices correspond to the $k$ -element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

In graph theory, a graph is said to be a pseudorandom graph if it obeys certain properties that random graphs obey with high probability. There is no concrete definition of graph pseudorandomness, but there are many reasonable characterizations of pseudorandomness one can consider.

The expander mixing lemma intuitively states that the edges of certain $-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .$

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices $v$ and $w$ , the number of vertices at distance $j$ from $v$ and at distance $k$ from $w$ depends only upon $j$ , $k$ , and the distance between $v$ and $w$ .

In group theory, a branch of mathematics, the automorphisms and outer automorphisms of the symmetric groups and alternating groups are both standard examples of these automorphisms, and objects of study in their own right, particularly the exceptional outer automorphism of S₆, the symmetric group on 6 elements.

In graph theory, a branch of mathematics, a crown graph on $2 n$ vertices is an undirected graph with two sets of vertices ${u 1, u 2, \dots, u n}$ and ${v 1, v 2, \dots, v n}$ and with an edge from $u i$ to $v j$ whenever $i \neq j$ .

In extremal graph theory, the forbidden subgraph problem is the following problem: given a graph $, find the maximal number of edges an -vertex graph can have such that it does not have a subgraph isomorphic to . In this context, is called a forbidden subgraph .$

In the mathematical field of graph theory, the odd graphs are a family of symmetric graphs defined from certain set systems. They include and generalize the Petersen graph.

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by $, using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph .$

In graph theory, Grassmann graphs are a special class of simple graphs defined from systems of subspaces. The vertices of the Grassmann graph $J q (n, k)$ are the $k$ -dimensional subspaces of an $n$ -dimensional vector space over a finite field of order $q$ ; two vertices are adjacent when their intersection is $(k - 1)$ -dimensional.

The method of (hypergraph) containers is a powerful tool that can help characterize the typical structure and/or answer extremal questions about families of discrete objects with a prescribed set of local constraints. Such questions arise naturally in extremal graph theory, additive combinatorics, discrete geometry, coding theory, and Ramsey theory; they include some of the most classical problems in the associated fields.

References

1 2 3 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 .
↑ 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 .
↑ "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
1 2 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, arXiv: 1406.0142 , Bibcode:2014arXiv1406.0142F, doi:10.37236/4567, S2CID 7416206 .
1 2 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 $r$-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}}: CS1 maint: location missing publisher (link)

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[hs93-1] 1 2 3 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 .

[2] Alspach, Brian (2013), "Johnson graphs are Hamilton-connected", Ars Mathematica Contemporanea, 6 (1): 21–23, doi: 10.26493/1855-3974.291.574 .

[3] Newman, Ilan; Rabinovich, Yuri (2015), On Connectivity of the Facet Graphs of Simplicial Complexes, arXiv: 1502.02232 , Bibcode:2015arXiv150202232N .

[4] Rispoli, Fred J. (2008), The graph of the hypersimplex, arXiv: 0811.2981 , Bibcode:2008arXiv0811.2981R .

[5] "Johnson", www.win.tue.nl, retrieved 2017-07-26

[6] 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

[:0-7] 1 2 Brouwer, Andries E. (1989), Distance-Regular Graphs, Cohen, Arjeh M., Neumaier, Arnold., Berlin, Heidelberg: Springer Berlin Heidelberg, ISBN 9783642743436, OCLC 851840609

[8] Filmus, Yuval (2014), "An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube", The Electronic Journal of Combinatorics, 23, arXiv: 1406.0142 , Bibcode:2014arXiv1406.0142F, doi:10.37236/4567, S2CID 7416206 .

[c99-9] 1 2 Cameron, Peter J. (1999), Permutation Groups, London Mathematical Society Student Texts, vol. 45, Cambridge University Press, p. 95, ISBN 9780521653787 .

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

[11] Christofides, Demetres; Ellis, David; Keevash, Peter (2013), "An Approximate Vertex-Isoperimetric Inequality for $r$-sets", The Electronic Journal of Combinatorics, 4 (20).

[12] Godsil, C. D.; Meagher, Karen (2016), Erdős-Ko-Rado theorems : algebraic approaches, Cambridge, United Kingdom, ISBN 9781107128446, OCLC 935456305 {{citation}}: CS1 maint: location missing publisher (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]