---
tag: 6P95Y8Z98A
kind: statement
role: lemma
name: Rainbow KKM lemma (Gale)
sources:
  - wikipedia: en:3963004@r1362920252
    locator: Knaster–Kuratowski–Mazurkiewicz lemma, section Generalizations > Rainbow KKM lemma (Gale)
    note: adopted
    mention: wikipedia://en/3963004#6UXP
    sections: [Statement]
inventory: [2Y6RAPN4HY]
---

## Statement

David Gale proved the following generalization of the KKM lemma. Suppose that, instead of one KKM covering, we have *n* different KKM coverings: $C^1_1,\ldots,C^1_n,\ldots,C^n_1,\ldots,C^n_n$. Then, there exists a permutation $\pi$ of the coverings with a non-empty intersection, i.e.:

$$\bigcap_{i=1}^{n}C^{\pi(i)}_i \neq \emptyset.$$

The name "rainbow KKM lemma" is inspired by Gale's description of his lemma:

> "A colloquial statement of this result is... if each of three people paint a triangle red, white and blue according to the KKM rules, then there will be a point which is in the red set of one person, the white set of another, the blue of the third".

The rainbow KKM lemma can be proved using a rainbow generalization of Sperner's lemma.

The original KKM lemma follows from the rainbow KKM lemma by simply picking *n* identical coverings.