Simplicial and Cubical Complexes Associated to Kneser Graphs

4 Simplicial and Cubical Complexes Associated to Kneser Graphs 

To finish the proof of the Kneser conjecture (Theorem 17.21), we still need to see that the neighborhood complex of Kneser graphs is sufficiently connected. In fact, it turns out that the homotopy type of these complexes can be determined precisely. 

Proposition 17.28. For arbitrary positive integers n and k such that n 2k, the abstract simplicial complex J f KGn,k) homotopy equivalent to a wedge 

On the other hand, it is easy to see that the image of the operator y consists of aU subsets S C [n] such that k 1-51 n — fc. In other words, the poset Im(9c) is a certain rank selection of the Boolean algebra B . By Proposition 12.6, see also specifically Example 12.10(2), we know that the order complex of that poset is homotopy equivalent to a wedge of spheres of dimension n — k)—k = n — 2k.  

Theorem 17.21 now foUows. Though this is a short and clarifying proof of Proposition 17.28, we shall investigate the complexes associated to Kneser graphs at some further length to imcover some interesting cubical constructions and to illustrate some other techniques that we developed in Part II. 

---