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:

1. The vertex set of $K{G}_{n,k}$ is the collection of $k$-element subsets of the fixed set of size $n$.
2. 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

Arithmetic functions

Size measures

Function	Value	Explanation
size of vertex set	$(\genfrac{}{}{0ex}{}{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}(\genfrac{}{}{0ex}{}{n}{k,k,n-2k})=\frac{1}{2}\frac{n!}{k!k!(n-2k)!}$	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-2k$.

Numerical invariants associated with vertices

We restrict attention to the case that $1<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	$(\genfrac{}{}{0ex}{}{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	If $k\le n/3$, it is 2 In general, it is something like twice the smallest integer greater than or equal to $k/(2(n-2k))$.

Other numerical invariants

Function	Value	Explanation
clique number	no easy formula, but generally grows with $q$	Note that $q=5$ is the only case where the clique number is 2; for $q\ge 9$, the clique number is at least 3 because of the presence of adjacent quadratic residues -- the number of adjacent quadratic residues is $(q-5)/4$. $q=17$ is the largest value for which the clique number is 3. By Ramsey theory, we know that if $q\ge R(m,m)$, then the clique number is at least $m$.
independence number	same as clique number	The two numbers are equal because the Paley graph is a self-complementary graph and independence number equals clique number of complement
chromatic number	Fill this in later	Fill this in later
radius of a graph	2	Due to vertex-transitivity, the radius equals the eccentricity of any vertex, which has been computed above.
diameter of a graph	2	Due to vertex-transitivity, the diameter equals the eccentricity of any vertex, which has been computed above.
girth of a graph	3 (except the case of $P_5$)	The girth of $P_5$ is 5. Note that for all higher $q$, the girth of the graph is 3, due to the fact that there are $(q-5)/4$ pairs of nonzero quadratic residues that differ by 1, and this number is positive whenever $q>5$.
circuit rank	$q(q-5)/4+1$ $=(q-1)(q-4)/4$	The circuit rank is number of edges - number of vertices + number of connected components. This becomes $q(q-1)/4-q+1$ which simplifies to $q(q-5)/4+1$.