2
$\begingroup$

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.

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

1 Answer 1

Reset to default
4
$\begingroup$

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

References

[B] Zs. Baranyai, On the factorization of the complete uniform hypergraph, In: Eds. A. Hajnal, R. Rado, and V. T. Sós, Infinite and Finite Sets (Proc. Intern. Coll. Keszthely, 1973), Bolyai J. Mat. Társulat, Budapest & North-Holland, Amsterdam, 1975, 91–108.

[BP] Boštjan Brešar, Mario Valencia-Pabon, Independence number of products of Kneser graphs, (November 19, 2018).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ i'm currently banned from MSE (for telling mods to stop removing the infowars link from my profile). what you said here is correct; thanks for catching those typos. feel free to make the appropriate edits $\endgroup$
    – mathworker21
    Commented Jul 30, 2020 at 14:56
  • 1
    $\begingroup$ @mathworker21 Done. $\endgroup$
    – Alex Ravsky
    Commented Jul 30, 2020 at 15:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .