Consideremos un gráfico cuyos vértices son cada uno de los $\frac{n!}{(n-k)!}$ $k$ -permutaciones de $n$ . Dos vértices comparten una arista si sus permutaciones (parciales) difieren exactamente en una posición. ¿Cuál es el número de independencia de este gráfico?
Sospecho que la respuesta es $\frac{n!}{(n-k+1)!}$ . Ciertamente no puede ser mayor que esto porque los vértices se pueden dividir en $\frac{n!}{(n-k+1)!}$ camarillas de $n-k+1$ vértices.
Un ejemplo: $k=2$ y $n=4$ . El número de 2-permutaciones de 4 es $\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)
Obsérvese que cada fila es una 3-clica en el gráfico porque las 3 permutaciones parciales difieren sólo en una posición. Cada vértice está en dos 3-cliques diferentes (por ejemplo, (1,2) está en un 3-clique con (1,3),(1,4), y con (3,2),(4,2)). El número de independencia no puede ser superior a $\frac{n!}{(n-k+1)!} = 4$ porque un conjunto independiente no puede incluir más de un vértice de cada fila anterior. Un conjunto independiente es
(1,2) (2,3) (3,4) (4,1).
En el caso general, las camarillas contienen $n-k+1$ vértices, y cada vértice está en $k$ tales camarillas.
Tengo soluciones para ciertos casos. Para $k=1$ el número de independencia es sólo 1. Para $k=2$ un conjunto independiente es (1,2) (2,3) ... ( $n$ -1, $n$ ) ( $n$ , 1). Esto hace que el número de independencia $n$ para $k=2$ . Para $k=n$ no hay aristas, por lo que el número de independencia es $n!$ . Para $k=n-1$ un conjunto independiente es el grupo alterno de $S_n$ con el último elemento de cada permutación eliminado para formar un $k$ -permutación de $n$ . He investigado otros subgrupos de $S_n$ para encontrar soluciones en otros casos. Esto a veces funciona, pero no siempre. Por ejemplo, $S_6$ no tiene ningún subgrupo de orden 30, pero he encontrado un conjunto independiente de 30 vértices para el $k=3$ , $n=6$ caso.
