Skip to content

Knaster–Kuratowski–Mazurkiewicz Lemma

A simplex-covering intersection theorem: if each face is covered by the closed sets indexed by that face’s vertices, then every indexed set shares a common point, converting boundary-compatible local coverage into global coexistence.

Version
v2 · 2026-09-19 · History
Domain-specific #
2135
Domain group
Formal Sciences
Origin domain
Mathematics
Subdomain
Fixed Point and Convexity Theory → Mathematics
Aliases
KKM lemma, KKM theorem, Knaster-Kuratowski-Mazurkiewicz lemma

Core Idea

The Knaster–Kuratowski–Mazurkiewicz (KKM) Lemma turns a boundary-compatible cover of a simplex into a common-intersection guarantee. Let Δ be an (n-1)-simplex with vertices v_1,...,v_n, and let C_1,...,C_n be closed subsets of Δ. If every face spanned by a nonempty index set I is covered by the sets carrying those same indices,

conv{v_i : i in I} subseteq union_{i in I} C_i,

then all the sets intersect: intersection_{i=1}^n C_i is nonempty.

The locked identity is simplex + one closed set per vertex + every face covered only by its eligible vertex-indexed sets -> at least one point belonging to every set.

How would you explain it like I'm…

The Every-Color Spot

Draw a triangle with a red corner, a blue corner and a yellow corner. Now color every spot in the triangle with one or more colors, following rules: each corner gets its own color, each spot on a side uses only the colors of that side's two corners, and inside you may use any of them. If you color this way, there will always be a spot that has all three colors at once.

Corner Colors Must Overlap

Take a triangle with corners numbered 1, 2 and 3, and pick a region of the triangle for each number (regions can overlap). The rule: corner 1 must be in region 1, every point on the edge between corners 1 and 2 must be in region 1 or region 2, and so on for every edge, and the whole triangle must be covered by the three regions. The Knaster–Kuratowski–Mazurkiewicz Lemma says that then some point belongs to all three regions at once. It's surprising: normally covering just means each point is in some region, but these edge rules force a point where they all meet. The same works for higher-dimensional triangle-like shapes.

Simplex Cover Intersection Lemma

A simplex is the generalization of a triangle: a segment, triangle, tetrahedron, and so on. The KKM lemma gives each vertex its own closed set. The hypothesis: for every face of the simplex, that face is covered by the sets belonging to that face's own vertices. The conclusion: there is a point lying in all the sets simultaneously. Equivalently, every point must belong to some set whose vertex has a positive 'weight' in that point's coordinates. This is stronger than plain covering, which only places each point somewhere; the face rule forces a common point. The lemma gives a proof of Brouwer's fixed-point theorem, but it is its own specific statement about covers of a simplex.

 

Let Δ be an (n−1)-simplex with vertices v₁,…,vₙ, and let C₁,…,Cₙ be closed subsets of Δ. The KKM condition requires that for every nonempty index set I, the face conv{vᵢ : i ∈ I} is contained in the union of the Cᵢ with i ∈ I. The Knaster–Kuratowski–Mazurkiewicz Lemma concludes that the intersection of all the Cᵢ is nonempty. In barycentric coordinates x = (x₁,…,xₙ), the hypothesis says each point lies in some Cᵢ with xᵢ > 0. Closedness matters, as does the restriction that each face is covered only by its own vertex-indexed sets. The lemma yields a proof of Brouwer's fixed-point theorem and sits in a family of results that are equivalent or closely interderivable under standard formulations, but the general idea of a fixed point does not imply this specific cover condition. It is also distinct from separation theorems about connected spaces such as the Phragmén–Brouwer theorem.

Scope of Application

KKM is a central tool in fixed-point theory, nonlinear analysis, minimax theory, variational inequalities, equilibrium existence, fair division, matching, and cooperative game theory. Its power is representational: a problem is reformulated so that each C_i means “index i is acceptable, selected, best responding, or nonviolating at this point.” Boundary conditions ensure that impossible or zero-weight indices are not the sole justification on a face. The total intersection produces a point where all indexed conditions coexist.

Clarity

The word “cover” occurs at two levels. Globally, all C_i cover Δ. Locally, a face may use only sets whose indices label vertices of that face. It is the local eligibility rule, not global coverage, that generates intersection.

Closedness enters only at the limiting step in the triangulation proof, but that does not make it cosmetic. Fully labeled mesh simplices can converge toward a boundary point missing from one nonclosed set.

Manages Complexity

Many existence problems ask for one point satisfying several coupled conditions. Direct construction is difficult because improving one condition can violate another. KKM replaces the simultaneous system with local covering obligations on faces. Each boundary face removes irrelevant indices, making the conditions easier to verify, and topology lifts those local facts to global coexistence.

Abstract Reasoning

  1. The singleton-face condition implies v_i in C_i for every vertex.
  2. Global coverage alone cannot imply total intersection; face eligibility supplies the missing force.
  3. If one C_i is not closed, a sequence of common approximate memberships can converge outside it.
  4. If all C_i are replaced by supersets while remaining closed, the KKM condition and conclusion persist.
  5. If an index has barycentric coordinate zero, the equivalent formulation requires some positive-coordinate label instead.

Knowledge Transfer

The exact abstraction transfers among fixed-point, equilibrium, minimax, fair-division, and matching problems when their feasible states form a simplex or justified generalization and indexed acceptability sets satisfy the face rule. A casual “local-to-global” analogy is not KKM without those roles.

The portable structural core is a constrained-cover intersection principle. Fixed Point, Compactness, Convexity, and Combinatorial Approximation carry the broader reasoning; barycentric coordinates and vertex-indexed faces supply the mathematical accent.

Relationships to Other Abstractions

Local relationship map for Knaster–Kuratowski–Mazurkiewicz LemmaParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Knaster–Kuratowski–M…DOMAINPrime abstraction: Fixed Point — includesFixed PointPRIME

Current abstraction Knaster–Kuratowski–Mazurkiewicz Lemma Domain-specific

Parents (1) — outgoing typed relations

  • Knaster–Kuratowski–Mazurkiewicz Lemma includes Fixed Point Prime

    KKM is a standard route to Brouwer and the broader fixed-point method.

Hierarchy path (1) — routes to 1 parentless root

  • Knaster–Kuratowski–Mazurkiewicz Lemma → includes Fixed Point

Neighborhood in Abstraction Space

Knaster–Kuratowski–Mazurkiewicz Lemma sits in a sparse region of the domain-specific corpus (86th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25