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.

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.