Skip to main content
added 10 characters in body
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

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.

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

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.

removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Independent sets in Complementcomplement of Kneser Graphsgraphs

added 1 character in body; edited title
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Inependent 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$ indpendentindependent sets in the complement of a kneserKneser 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 kneserKneser 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 kneserKneser 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.

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.

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

edited body
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22
Loading
added 25 characters in body
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22
Loading
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22
Loading