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.^[1]

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. Equivalently, in barycentric coordinates x = (x_1,...,x_n), every point belongs to at least one C_i whose coordinate x_i is positive. The conclusion is surprising because ordinary covering guarantees only that each point lies somewhere; the face restriction forces the locally eligible memberships to coexist globally.

The KKM lemma is domain-specific mathematics rather than a prime. It composes with Fixed Point: KKM supplied a proof of Brouwer’s fixed-point theorem and belongs to a family of results equivalent or closely interderivable under standard formulations. The live Fixed Point prime does not entail this simplex-indexed cover condition. Nor does the accepted Phragmén–Brouwer theorem duplicate it: that theorem concerns separation properties of connected spaces, not face-compatible covers of a simplex.

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.

Structural Signature

• an (n-1)-simplex Δ — the convex hull of affinely independent vertices v_1,...,v_n;
• vertex indices [n] — one label connects vertices, coordinates, faces, and covering sets;
• barycentric coordinates — each point has nonnegative coordinates summing to one;
• one set C_i per vertex — membership alternatives share the simplex’s indexing system;
• closedness — each C_i contains its relevant limit points;
• every nonempty face — for I subseteq [n], Δ_I = conv{v_i : i in I} includes vertices, edges, and higher faces;
• eligible-cover condition — Δ_I is covered by union_{i in I} C_i, never requiring a set indexed outside the face;
• boundary compatibility — a point with x_i = 0 cannot rely solely on label i to satisfy the equivalent support condition;
• full-simplex coverage — the case I=[n] ensures the sets cover all of Δ;
• vertex anchoring — the singleton face {v_i} lies in C_i;
• finite index structure — there are exactly as many sets as vertices;
• compactness — the finite-dimensional closed simplex supports passage from approximating points to a limit;
• a combinatorial approximation route — fine triangulations and Sperner labels can encode the cover;
• a limiting argument — fully labeled small simplices shrink toward a point in all C_i;
• nonempty total intersection — existence, not uniqueness or measure, is guaranteed.

Checking only the vertices or the full simplex is insufficient. The condition ranges over every face and restricts which indexed sets may cover that face.

What It Is Not

• Not an arbitrary finite-cover theorem. A compact space can be covered by closed sets with empty total intersection.
• Not Helly’s theorem. Helly assumes intersection conditions on subfamilies of convex sets; KKM assumes face coverage and does not require the C_i themselves to be convex.
• Not Sperner’s lemma. Sperner is a combinatorial labeling theorem on triangulations, commonly used to prove KKM.
• Not Brouwer’s theorem itself. Brouwer asserts a fixed point for a continuous self-map; KKM asserts intersection under a cover condition.
• Not the KKMS theorem. Shapley’s generalization indexes sets by all nonempty subsets and concludes intersection for a balanced family.
• Not the rainbow KKM lemma. That result selects differently indexed sets from several KKM covers.
• Not true after silently dropping topology. Closedness, or an appropriate open-cover dual formulation, is load-bearing.
• Not a uniqueness theorem. The common intersection may contain many points.
• Not a constructive algorithm by itself. Existence can be nonconstructive even when a triangulation proof suggests approximation.

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.^[2]

For n=3, Δ is a triangle. C_1 contains vertex 1, C_2 vertex 2, and C_3 vertex 3. Edge 12 is covered by C_1 union C_2, edge 23 by C_2 union C_3, edge 31 by C_3 union C_1, and the triangle by all three. The conclusion forces a point of all three sets.

A standard proof triangulates the simplex finely. Each triangulation vertex is assigned an eligible label i for which it belongs to C_i. The face condition makes this a Sperner labeling. Sperner’s lemma yields a fully labeled small simplex. Repeating at finer meshes, compactness gives a convergent subsequence. Closedness puts the limit in every C_i.^[3]

Alternative formulations use open sets with modified hypotheses, set-valued maps, convex spaces, or KKM mappings. Those should be stated independently; the finite closed-cover lemma is the locked core.

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. The theorem may have dual open formulations, yet mixing the hypotheses of one with the conclusion of another is invalid.

The total intersection is stronger than pairwise intersection. For three or more sets, every pair may meet while all together do not. KKM forces the full family to share a point through the geometry of the indexed cover.

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.

This is also why the theorem travels to economics. Simplex coordinates can represent mixed strategies, resource shares, or probability weights. If an index with zero weight cannot be the sole justification for a point, the face condition encodes feasibility at the boundary; the intersection then supplies an equilibrium-like point.

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.
6. A fully labeled triangulation cell approximates simultaneous membership more closely as mesh diameter tends to zero.
7. Compactness provides a limit point; closedness transfers every repeated membership to the limit.
8. The theorem guarantees existence but gives no canonical choice among multiple common points.
9. Permuting vertex labels and their associated sets leaves the statement invariant.
10. A proposed application fails if its sets cover the interior but violate even one lower-dimensional face condition.

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.

Examples

• triangle cover: each edge uses only its endpoint colors, forcing a tricolor point;
• Brouwer proof: assume no fixed point, construct KKM sets or labels from displacement, and derive contradiction;
• simplex preferences: C_i records states where option i meets a best-response or acceptability condition;
• fair division: barycentric coordinates represent allocations and KKM sets represent agents’ acceptable pieces;
• rainbow variant: select one color-indexed set from each of several covers with common intersection;
• KKMS: sets indexed by coalitions yield a balanced intersecting subfamily;
• non-example—three disks: disks cover a triangle but ignore face eligibility and can lack a triple intersection;
• failure—open central omission: sets approach a central common point but one excludes its boundary;
• failure—unchecked edge: vertices and interior are covered, yet an edge relies on the opposite vertex’s set.

Structural Tensions

• local eligibility vs. global coexistence — face-wise alternatives force a simultaneous point;
• combinatorial finiteness vs. topological limit — Sperner supplies discrete witnesses and compactness produces an exact one;
• closedness vs. approximation — near-common points are inadequate unless membership survives limits;
• existence vs. construction — the lemma certifies a point without selecting or efficiently computing one;
• simplex specificity vs. generalization — barycentric faces make the core transparent while broader KKM spaces increase reach;
• strong intersection vs. weak assumptions on shape — covering sets need not be convex, but their index geometry is highly constrained.

Structural–Framed Character

The KKM Lemma is fully structural. The theorem’s objects, hypotheses, and conclusion are formal and invariant under relabeling or affine representation of the simplex.

Structural Core vs. Domain Accent

The structural core is boundary-compatible indexed local coverage -> unavoidable global overlap. The domain accent is a finite-dimensional simplex, vertex labels, barycentric faces, closed subsets, and topological intersection.

Instantiates / Related Primes

This entry is part of Fixed Point.

• Fixed Point — KKM is a standard route to Brouwer and to the broader fixed-point method.
• Compactness — convergent subsequences turn arbitrarily fine approximations into exact membership.
• Intersection — the conclusion is nonemptiness of a whole-family intersection.
• Convexity — faces and barycentric coordinates organize the eligibility condition.
• Local-to-Global Principle — constraints verified on all faces yield a simplex-wide conclusion.

The relation to Fixed Point is compositional rather than one of kind: KKM is an equivalent route to an intersection theorem, and is not itself syntactically a fixed-point assertion.

Relationships to Other Abstractions

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 (86^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Simplex — 0.82
• Polytope — 0.81
• Roman Dominating Set — 0.81
• Nut Graph — 0.80
• Goldberg–Seymour Theorem — 0.80

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

Not to Be Confused With

• Sperner’s lemma;
• Brouwer fixed-point theorem;
• Helly’s theorem;
• finite intersection property generally;
• KKMS theorem;
• rainbow KKM lemma;
• KKM mappings in every generalized convex space;
• Phragmén–Brouwer theorem;
• arbitrary covers of compact spaces.

References

[1] Bronisław Knaster, Kazimierz Kuratowski, and Stefan Mazurkiewicz, “Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe,” Fundamenta Mathematicae 14 (1929), 132–137, https://doi.org/10.4064/fm-14-1-132-137. registry ↩

[2] Sehie Park, “From Simplices to Abstract Convex Spaces: A Brief History of the KKM Theory,” Results in Nonlinear Analysis 1(1) (2018), 1–12, https://www.nonlinear-analysis.com/index.php/pub/article/view/3. registry ↩

[3] Emanuel Sperner, “Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes,” Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 6 (1928), 265–272, https://doi.org/10.1007/BF02940617. registry ↩

[4] “Knaster–Kuratowski–Mazurkiewicz lemma,” Wikipedia, frozen evidence packet, https://en.wikipedia.org/wiki/Knaster%E2%80%93Kuratowski%E2%80%93Mazurkiewicz_lemma. registry