Baranyai's Theorem

A complete graph is broken down into perfect matchings . That this is possible is the simplest case of Baranyai's theorem.

The set of Baranyai is a mathematical theorem in the field of combinatorics . It is named after the Hungarian mathematician Zsolt Baranyai , who proved the theorem in 1973. The starting point for the question dealt with by the sentence is the round- robin tournament known from many sports leagues . Several teams should play games on different game days in such a way that each team has exactly one game per game day and at the end each team has played exactly once against each other. For this to work, the number of all teams must obviously be even (otherwise not every team could play exactly one game per game day). However, it is by no means clear that this is enough to make such a game plan possible. The simplest case of Baranyai's theorem says that it is actually possible. The sentence generalizes the statement by not only dealing with the case that two teams are supposed to meet each other, but also making analogous statements for groups of larger numbers, for example a skat tournament in which each possible group of three should play together exactly once.

statement

Baranyai's theorem can be formulated in different ways. The graph theoretical formulation reads: The complete hypergraph has a 1-factorization if and only if is a divisor of . Here consists of nodes that are connected by hyperedges. A hyperedge connects nodes that the graph is complete, means that all possible edges appear in it. A 1-factor is a set of hyper-edges, so that each node is touched by exactly one edge. A 1-factorization of the graph is a disjoint decomposition of its edges into 1-factors. ${\ displaystyle K_ {n} ^ {m}}$ ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle K_ {n} ^ {m}}$ ${\ displaystyle n}$ ${\ displaystyle m}$

The statement can thus be reformulated with sets alone: Be a -element set. We are looking for families of subsets of such that: ${\ displaystyle A}$ ${\ displaystyle n}$ ${\ displaystyle M}$ ${\ displaystyle {\ mathcal {A}} _ {1}, \ ldots, {\ mathcal {A}} _ {M}}$ ${\ displaystyle A}$

The elements of are -elementary subsets of , each such subset occurs in exactly one .

{\ displaystyle {\ mathcal {A}} _ {i}}

{\ displaystyle m}

{\ displaystyle A}

{\ displaystyle {\ mathcal {A}} _ {i}}

Each is a partition of , so the sets it contains are disjoint, their union is . ${\ displaystyle {\ mathcal {A}} _ {i}}$ ${\ displaystyle A}$ ${\ displaystyle A}$

Baranyai's theorem says that such families exist if and only if is a divisor of and holds. ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle M = {n-1 \ choose m-1}}$

proof

The proof for one direction of the equivalence proposition is very easy: If such families of sets exist, then they must all contain the same number of subsets, which is number . From the fact that these are partitions it follows that there is a divisor of . Together the families contain subsets. There are -element subsets of , so . ${\ displaystyle k}$ ${\ displaystyle km = n}$ ${\ displaystyle m}$ ${\ displaystyle n}$ ${\ displaystyle kM}$ ${\ displaystyle {n \ choose m}}$ ${\ displaystyle m}$ ${\ displaystyle A}$ ${\ displaystyle M = {\ frac {n \ choose m} {k}} = {\ frac {m} {n}} {n \ choose m} = {n-1 \ choose m-1}}$

There is various evidence for the other, more difficult direction. Most of these proofs show a generalized statement that has no independent applications, but allows a proof by means of full induction on a variable that does not appear in the original statement. The idea of Andries Brouwer and Alexander Schrijver , who used the Max-Flow-Min-Cut theorem to prove the induction step , has found particular popularity .

history

The case was already known in the 19th century. Rose Peltesohn provided the first evidence of the case in 1936. The general case was known as the Sylvester Conjecture until Baranyai proved the theorem in 1973. His proof was published two years later. There are now a number of different proofs for the theorem, as well as various generalizations. ${\ displaystyle m = 2}$ ${\ displaystyle m = 3}$

Applications

From a constructive proof of Baranyai's theorem, a game plan for a round-robin tournament could actually be created, but much simpler construction methods are also known. In reality there are also many constraints that have to be met, so that algorithms from combinatorial optimization have to be used.

The sentence is also used in information theory .

The theorem has an internal mathematical application in determining the number of cliques in Kneser graphs .

Individual evidence

^ Sigrid Knust: Construction methods for sports league schedules. Retrieved February 11, 2015.
^ Ulrich Tamm: Applications of Baranyai's Theorem in Information Theory. In: AJ Han Vinck, Adriaan van Wijngaarden (Ed.): Proceedings of 6th Benelux-Japan Workshop on Coding and Information Theory. Essen, 1996. ( online )

literature

Zsolt Baranyai: On the Factorization of the Complete Uniform Hypergraph. In: András Hajnal , Richard Rado , Vera T. Sós : Infinite and Finite Sets. Amsterdam, 1975. pp. 91-108.
Andries Brouwer, Alexander Schrijver: Uniform Hypergraphs. In: Packing and Covering in Combinatorics. Mathematical Center Tracts, No. 106, 1979. pp. 39-73.
Dieter Jungnickel , Konrad Jacobs : Introduction to combinatorics. de Gruyter, 2nd edition 2004, ISBN 3-11-008736-7 . 3.4: The Baranyai theorem.

Web links

Eric W. Weisstein : Baranyai's Theorem . In: MathWorld (English).

[1] Sigrid Knust: Construction methods for sports league schedules. Retrieved February 11, 2015.

[2] Ulrich Tamm: Applications of Baranyai's Theorem in Information Theory. In: AJ Han Vinck, Adriaan van Wijngaarden (Ed.): Proceedings of 6th Benelux-Japan Workshop on Coding and Information Theory. Essen, 1996. ( online )