Generate Schrijver graphs and $s$-stable Kneser graphs

Generate all $k$-element subsets of $[n]:=\{1,2,\ldots,n\}$ with the property that any two 1s have cyclical distance at least $s$.
Size $n$ of ground set (max. 20)
Size $k$ of subsets (between 1 and $n$)
Distance $s$ of elements (at least 2)
Output format
Output  numbering graphics

Object info

For integers $k\geq 1$ and $n\geq 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $[n]:=\{1,2,\ldots,n\}$, and an edge between any two disjoint sets. The Schrijver graph $S(n,k)$ is an induced subgraph of $K(n,k)$, given by all sets in which no two elements are cyclically adjacent. More generally, for integers $k\geq 1$, $s\geq 1$ and $n\geq \max\{2,s\}k+1$, the $s$-stable Kneser graph $S(n,k,s)$ is an induced subgraph of $K(n,k)$, given by all sets in which any two elements have cyclical distance at least $s$. Note that the Kneser graph is precisely the $1$-stable Kneser graph, i.e., $K(n,k)=S(n,k,1)$. Furthermore, the Schrijver graph is precisely the $2$-stable Kneser graph, i.e., $S(n,k)=S(n,k,2)$. The figure below shows the Petersen graph $K(5,2)$, and the red subgraph is the Schrijver graph $S(5,2)$, with vertices represented by their characteristic vectors.

Schrijver graphs $S(n,k)$ were first investigated by Schrijver [Sch78], and he proved that they have the same chromatic number as the Kneser graph $K(n,k)$, namely $n-2k+2$. Furthermore, $S(n,k)$ is a vertex-critical subgraph of $K(n,k)$, i.e., removing any of its vertices creates a graph with strictly smaller chromatic number.

The algorithm running on this website generates a Hamilton cycle in $S(n,k,s)$ for arbitrary integers $k\geq 1$, $s\geq 2$ and $n\geq sk+1$, as described in the paper [MN24]. In the output, each set is represented by its corresponding characteristic vector. So far, no efficient algorithm is known for the case $s=1$, i.e., for Kneser graphs, even though they were shown to admit a Hamilton cycle for all $k\geq 1$ and $n\geq 2k+1$ [MMN23], with one notable exception, namely the Petersen graph $K(5,2)$ shown above.

Enumeration (OEIS)

The number of vertices of the Schrijver graph $S(n,k)$ equals $\binom{n-k+1}{k}-\binom{n-k-1}{k-2}$, which is the $(k+1)$st diagonal (from top-left to bottom-right) in the (2,1)-Pascal triangle; see OEIS A029653.

Download source code

[Zipped C++ source code (GNU GPL)]

References