Baranyai's Theorem

If k|n, then the complete k-uniform hypergraph on n vertices decomposes into 1-factors, where a 1-factor is a set of n/k pairwise disjoint k-sets. Brouwer and Schrijver (1979) give a beautiful proof using the maximum flow, minimum cut theorem of network flows.

This theorem can be applied to finding the clique number of a Kneser graph.

See also

Kneser Graph

Explore with Wolfram|Alpha


Baranyai, Z. "On the Factorization of the Complete Uniform Hypergraph. Infinite and Finite Sets." In Infinite and Finite Sets, Vol. 1. Proceedings of a Colloquium held at Keszthely, June 25-July 1, 1973. Dedicated to Paul Erdős on his 60th Birthday (Ed. A. Hajnal, R. Rado, and V. T. Sós). Amsterdam, Netherlands: North-Holland, pp. 91-108, 1975.Brouwer, A. E. and Schrijver, A. "Uniform Hypergraphs." In Packing and Covering in Combinatorics. Mathematical Centre Tracts, No. 106, pp. 39-73, 1979.Tamm, U. "Applications of Baranyai's Theorem in Information Theory." In Proceedings of 6th Benelux-Japan Workshop on Coding and Information Theory, Essen, 1996 (Ed. A. J. Han Vinck and A. van Wijngaarden). Shannon Foundation, 1996. Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, pp. 476-479, 1993.West, D. "Re: disjoint cliques, resolutions of designs?" posting. Feb. 25, 2004.

Referenced on Wolfram|Alpha

Baranyai's Theorem

Cite this as:

Weisstein, Eric W. "Baranyai's Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications