Skip to main content
3 of 6
edited body
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Inependent 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$ indpendent 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$ 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.

vidyarthi
  • 2.1k
  • 1
  • 16
  • 22