# Independence number of a graph based on $k$-permutations of $n$

Consider a graph whose vertices are each of the $\frac{n!}{(n-k)!}$ $k$-permutations of $n$. Two vertices share an edge if their (partial) permutations differ in exactly one position. What is the independence number of this graph?

I suspect the answer is $\frac{n!}{(n-k+1)!}$. It certainly can't be larger than this because the vertices can be divided into $\frac{n!}{(n-k+1)!}$ cliques of $n-k+1$ vertices.

An example: $k=2$ and $n=4$. The number of 2-permutations of 4 is $\frac{n!}{(n-k)!} = 12$:
(1,2) (1,3) (1,4)
(2,1) (2,3) (2,4)
(3,1) (3,2) (3,4)
(4,1) (4,2) (4,3)

Note that each row is a 3-clique in the graph because all 3 partial permutations differ in only one position. Each vertex is in two different 3-cliques (e.g., (1,2) is in a 3-clique with (1,3),(1,4), and with (3,2),(4,2)). The independence number cannot exceed $\frac{n!}{(n-k+1)!} = 4$ because an independent set cannot include more than one vertex from each row above. One independent set is
(1,2) (2,3) (3,4) (4,1).

In the general case, the cliques contain $n-k+1$ vertices, and each vertex is in $k$ such cliques.

I have solutions for certain cases. For $k=1$, the independence number is just 1. For $k=2$, an independent set is (1,2) (2,3) ... ($n$-1,$n$) ($n$, 1). This makes the independence number $n$ for $k=2$. For $k=n$, there are no edges, so the independence number is $n!$. For $k=n-1$, an independent set is the alternating group of $S_n$ with the last element of each permutation dropped to form a $k$-permutation of $n$. I investigated other subgroups of $S_n$ to find solutions in other cases. This sometimes works, but not always. For example, $S_6$ has no subgroup of order 30, but I have found an independent set of 30 vertices for the $k=3$, $n=6$ case.

• All k permutations of n are exactly k elements long, with the elements chosen from {1,...,n} without repetition. – Michael Wiener Apr 1 '18 at 21:08