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

v1 · 2026-08-30 · History

Domain-specific #

2135

Origin domain

mathematics

Subdomain

fixed point and convexity theory

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.

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

Current abstraction Knaster–Kuratowski–Mazurkiewicz Lemma Domain-specific

Parents (1) — more general patterns this builds on

• Knaster–Kuratowski–Mazurkiewicz Lemma is part of 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 → Fixed Point

Neighborhood in Abstraction Space

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

Family — Graph Coloring Games & Drawings (7 abstractions)

Nearest neighbors

• Simplex — 0.82
• Nut Graph — 0.80
• Goldberg–Seymour Theorem — 0.80
• Degree diameter problem — 0.80
• Graph Sphericity — 0.80

Computed from structural-signature embeddings · 2026-09-08