Baranyai's theorem¶

The theorem that a complete uniform hypergraph can be decomposed into perfect matchings whenever the edge size divides the number of vertices.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3413
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Combinatorial Design → Mathematics

Core Idea¶

The divisibility condition is necessary for one-factorization, notation for vertex count and uniformity varies, and the theorem’s full generalization can balance factors even when exact division fails. All fixed-size subsets of a finite vertex set are partitioned into classes, each class itself partitioning the vertices; combinatorial construction distributes every hyperedge exactly once among these one-factors. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Every Team Plays Once

Imagine a class of kids, and you want every possible team of the same size to play exactly once. If the class splits evenly into teams of that size, Baranyai's theorem says you can sort all those possible teams into rounds. In each round every kid is on exactly one team, and by the end every possible team has played once.

Sorting All Teams into Rounds

Suppose you have n players and you want every possible group of exactly k players to meet once. Baranyai's theorem says this can be scheduled in rounds where, in each round, the groups don't overlap and every player is in exactly one group. That only works if k divides n evenly, since otherwise one round can't use everyone with no one left over. The theorem promises that whenever k does divide n, a perfect schedule always exists, using every possible group exactly once. The familiar case of pairs (k = 2) is the classic round-robin tournament with an even number of players.

Hypergraph One-Factorization Theorem

Take a set of n points and look at every subset of exactly k points; these subsets are the edges of the complete k-uniform hypergraph, a generalization of a graph in which edges can join more than two points. A one-factor, also called a perfect matching, is a collection of pairwise disjoint edges that together cover every point. Baranyai's theorem says that if k divides n, the set of all k-subsets can be partitioned into one-factors, so every k-subset belongs to exactly one of them. The divisibility condition is necessary, since a one-factor must split the n points into groups of size k. When k = 2, this recovers the familiar fact that a complete graph with an even number of vertices has a one-factorization, like a round-robin schedule. A more general version of the theorem balances the edges among factors even when k does not divide n.

Let K_n^k denote the complete k-uniform hypergraph whose vertices are an n-element set and whose hyperedges are all k-subsets. A one-factor is a set of pairwise disjoint hyperedges covering every vertex, so it has n/k edges, and a one-factorization is a partition of all hyperedges into one-factors. Baranyai's theorem states that K_n^k has a one-factorization whenever k divides n; counting shows there are then C(n, k)·k/n = C(n−1, k−1) one-factors. Divisibility is necessary, since a single one-factor partitions the vertex set into k-blocks. The case k = 2 recovers the one-factorization of the complete graph K_n for even n. The full generalization goes further: it distributes hyperedges among classes in a balanced way even when exact division fails. Because notation for n and k varies between sources, a correct statement fixes which symbol is the vertex count and which is the edge size.

Scope of Application¶

Baranyai's theorem belongs to combinatorial design and is useful where the analyst can specify the typed combinatorial design carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, then evaluate the vertex count n and uniform edge size k with k dividing n, complete k-uniform hypergraph, hyperedges as all k-subsets, one-factor as pairwise disjoint edges covering every vertex, factorization as an edge partition, number and size of factors, divisibility necessity, graph special case and balanced generalization are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the vertex count n and uniform edge size k with k dividing n, complete k-uniform hypergraph, hyperedges as all k-subsets, one-factor as pairwise disjoint edges covering every vertex, factorization as an edge partition, number and size of factors, divisibility necessity, graph special case and balanced generalization are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Baranyai's theorem. Baranyai's theorem compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed combinatorial design carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the vertex count n and uniform edge size k with k dividing n, complete k-uniform hypergraph, hyperedges as all k-subsets, one-factor as pairwise disjoint edges covering every vertex, factorization as an edge partition, number and size of factors, divisibility necessity, graph special case and balanced generalization are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of combinatorial design because they reuse the typed combinatorial design carrier, including objects, relations, parameters, conventions, evidence, boundaries, and comparison targets, All fixed-size subsets of a finite vertex set are partitioned into classes, each class itself partitioning the vertices; combinatorial construction distributes every hyperedge exactly once among these one-factors., and type the carrier, state every parameter and convention in the definition, test that the vertex count n and uniform edge size k with k dividing n, complete k-uniform hypergraph, hyperedges as all k-subsets, one-factor as pairwise disjoint edges covering every vertex, factorization as an edge partition, number and size of factors, divisibility necessity, graph special case and balanced generalization are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Baranyai's theorem Domain-specific

Parents (1) — outgoing typed relations

Baranyai's theorem is a kind of Decomposition Prime

It remains its own entry because its identity is fixed by the vertex count n and uniform edge size k with k dividing n, complete k-uniform hypergraph, hyperedges as all k-subsets, one-factor as pairwise disjoint edges covering every vertex, factorization as an edge partition, number and size of factors, divisibility necessity, graph special case and balanced generalization.

Hierarchy path (1) — routes to 1 parentless root

Baranyai's theorem → is a kind of Decomposition

Neighborhood in Abstraction Space¶

Baranyai's theorem sits in a crowded region of the domain-specific corpus (13^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Combinatorial Optimization on Graphs (16 abstractions)

Nearest neighbors

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