Kneser graph

Definition

Suppose $n$ and $k$ are positive integers. The Kneser graph $K G_{n, k}$ is an undirected graph defined as follows. Fix a set of size $n$ (we usually take the set as ${1, 2, \dots, n}$ for convenience). Then:

The vertex set of $K G_{n, k}$ is the collection of $k$ -element subsets of the fixed set of size $n$ .
The edge set of $K G_{n, k}$ is defined as follows: two vertices of $K G_{n, k}$ are adjacent if and only if they are disjoint when viewed as subsets of the $n$ -element set.

Particular cases

Classes of cases

Condition on $n$ and $k$	Conclusion
$k > n$	The vertex set is empty, so the graph is a graph on no vertices
$k = n$	one-point graph
$n / 2 < k < n$	The vertex set is non-empty, but the edge set is empty, so the graph is an empty graph
$k = n / 2$	In this case, the graph is a matching graph: it is a disjoint union of 2-cliques, with one 2-clique for each partition of the $n$ -set into two disjoint pieces of equal size.
$1 < k < n / 2$	This is the interesting case. In this case, the graph is connected and non-empty, but is not a complete graph.
$k = 1$	complete graph $K_{n}$
$k = 0$	one-point graph

First few nontrivial cases

As indicated above, the interesting cases are where $1 < k < n / 2$ . We list the first few of these:

$n$	$k$	Kneser graph $K G_{n, k}$
5	2	Petersen graph
6	2	Fill this in later

Odd graph case

A particular case of Kneser graphs of interest is where $n = 2 k + 1$ . This gives a one-parameter family of graphs called odd graphs. Specifically, the odd graph $O_{m}$ is defined as the Kneser graph with $n = 2 m - 1$ and $k = m - 1$ .

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	$(\binom{n}{k}) = \frac{n!}{k! (n - k)!}$	By definition, it is the number of $k$ -element subsets of a fixed $n$ -element set.
size of edge set	$\frac{1}{2} (\binom{n}{k, k, n - 2 k}) = \frac{1}{2} \frac{n!}{k! k! (n - 2 k)!}$	This is the number of ways of dividing a set of size $n$ into two interchangeable substs of size $k$ and a left-over set of size $n - 2 k$ .

Numerical invariants associated with vertices

We restrict attention to the case that $1 \leq k < n / 2$ for the expressions below.

Since the graph is a vertex-transitive graph, any numerical invariant associated to a vertex must be equal on all vertices of the graph. Below are listed some of these invariants:

Function	Value	Explanation
degree of a vertex	$(\binom{n - k}{k})$	We need to determine, for a given $k$ -element subset, the number of $k$ -element subsets disjoint from it. This is the same as the number of $k$ -element subsets of its set-theoretic complement, which has size $n - k$ .
eccentricity of a vertex	$1 + ⌈ \frac{k - 1}{n - 2 k} ⌉$ where $⌈ ⌉$ denotes the ceiling function: the smallest integer greater than or equal to a given number

Other numerical invariants

We restrict attention to the case $1 \leq k < n / 2$ for all the formulas below, though some of the formulas are also more generally valid.

Function	Value	Explanation
clique number	$⌊ \frac{n}{k} ⌋$ where $⌊ ⌋$ is the floor function (the greatest integer function) that returns the largest integer less than or equal to the number	For a subset of the vertex set to form a clique, the elements of the subset must be disjoint as subsets of the $n$ -element set. If there are $r$ such subsets, they have a total of $k r$ elements, forcing $k r \leq n$ , giving the upper bound. It's also easy to see that this upper bound is achieved.
independence number	Fill this in later
chromatic number	$n - 2 k + 2$ if $k \leq n / 2$ 1 otherwise
radius of a graph	$1 + ⌈ \frac{k - 1}{n - 2 k} ⌉$ where $⌈ ⌉$ denotes the ceiling function: the smallest integer greater than or equal to a given number	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	$1 + ⌈ \frac{k - 1}{n - 2 k} ⌉$ where $⌈ ⌉$ denotes the ceiling function: the smallest integer greater than or equal to a given number	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
odd girth	$1 + 2 ⌈ \frac{k}{n - 2 k} ⌉$ where $⌈ ⌉$ denotes the ceiling function: the smallest integer greater than or equal to a given number
even girth	6 if $n = 2 k + 1$ 4 if $n \geq 2 k + 2$