Lovasz conjecture

Fig. 19.2. A cochain whose coboundary equals the power of the characteristic class. Theorem 19.15. (Lovasz conjecture).

The Lovasz conjecture (here Theorem 19.15) was from the very beginning an important motivation for developing the theory of Horn complexes. It was originally settled by Babson and the author in a series of papers [BK03, BK06, BK04]. 

The Kneser conjecture states that in fact equality holds. This was proved in 1978 by L. Lovasz, who used geometric obstructions of Borsuk-Ulam type to show the nonexistence of certain graph colorings. 

Lovasz has introduced the neighborhood complex N G) as a part of his topological approach to the resolution of the Kneser conjecture. The hard part of the proof is to show the inequality x En,k) > n — 2k + 2, and Lovasz s idea was to use the connectivity information of the topological space Af G) to find obstructions to the vertex-colorability of G. More precisely, he proved the following statement. 

---