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

Question

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.

Answer 1

I have just been studying a problem that I believe is equivalent to yours. Working with Piotr Zielinski and Rob Pratt I can say that the independence number is 1/3 of the vertex count in the cases n=5, k=3; n=6, k=4; n=7;k=5; n=8, k=6. I am working hard on the (9,7) case. If you have any more information on this general topic or just want to get in touch, please send me a private message. If that is not possible on this site, you can find my e-addresse at the math dept at macalester college.

Stan Wagon

Answer 2

Such graphs are called arrangement graphs $A_{n,k}$. Your intuition about the independence number is correct. The independence number of $A_{n,k}$ is $\frac{n!}{(n-k+1)!}$. See corollary 3.6 of the following paper:

Liu et al., A Note of Independent Number and Domination Number of $Q_{n,k,m}$-Graph, Parallel Processing Letters (2019).

Note: In that paper, they prove this result for the superclass of $Q_{n,k,m}$ graphs which may be of interest to you if you are working on networks.