# Independent sets in complement of Kneser graphs

Intuition strongly suggests that there exist $$\left\lfloor\frac{\binom{n}{k}}{\lfloor\frac{n}{k}\rfloor}\right\rfloor$$ independent sets in the complement of a Kneser graph each having $$\lfloor\frac{n}{k}\rfloor$$ vertices in it. Is this true. If true, how to establish it?

A construction of such a set of cliques in the Kneser graph $$K(6,2)$$ is as follows: $$(12)(34)(56)$$ $$(13)(25)(46)$$ $$(14)(26)(35)$$ $$(15)(24)(36)$$ $$(16)(23)(45)$$ Thus, in this example we have $$5$$ disjoint triangles in the Kneser graph $$K(6,2)$$ which correspond to an equitable $$5$$ coloring of the complement graph $$\overline{K}(6,2)$$. Can such a construction be always done? I think this is related to the number of order $$2$$ elements in the symmetric group of order $$n$$. Thanks beforehand.

• How would you interpret the case of $n=7$ and $k=3$? Commented Jun 15, 2020 at 10:20
• @LeechLattice edited. please see now Commented Jun 15, 2020 at 10:41
• @RobPratt yes, that is what I have said in the post Commented Jun 15, 2020 at 15:48

According to [p. 8], Baranyai's theorem [B] implies that the vertex set of the Kneser graph $$K(n,k)$$ can be partitioned into $$\left\lceil\frac{\binom{n}{k}}{\left\lfloor\frac{n}{k}\right\rfloor}\right\rceil$$ cliques of size $$\left\lfloor\frac{n}{k}\right\rfloor$$.