Van der Waerden's theorem (decomposition of finite sets)

The Van der Waerden's theorem on the finite amounts of decomposition is a mathematical theorem which both of the set theory, and the graph theory may be attributed. He goes back to the Dutch mathematician Bartel Leendert van der Waerden , of him in 1927 published . The theorem deals with the decomposition of finite sets and is closely related to a graph theory theorem by the Hungarian mathematician Dénes Kőnig about regular bipartite graphs from 1914.

Formulation of the sentence

The sentence can be stated as follows:

Given are two natural numbers and a finite basic set with elements . ${\displaystyle n,k\in \mathbb {N} }$ ${\displaystyle X}$ ${\displaystyle n\cdot k}$

Let two decompositions be given and of the same size in classes; so in such a way that the equations are always fulfilled. ${\displaystyle {\mathcal {A}}=(A_{1},\ldots ,A_{n})}$ ${\displaystyle {\mathcal {B}}=(B_{1},\ldots ,B_{n})}$ ${\displaystyle X}$ ${\displaystyle |A_{i}|=k=|B_{j}|\;(i,j=1,\ldots ,n)}$

Then:

Have under these circumstances and always a common representative system ; So a representative system such that each class and each class is represented by exactly one of these representatives. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

Corollary: Miller's theorem

BL van der Waerden found and formulated his theorem as a direct generalization of a group-theoretical theorem by the American mathematician George Abram Miller . Miller's theorem results from applying van der Waerden's theorem to the right and left secondary classes of the subgroups of finite groups . Put together, Miller's theorem says:

In a finite group there is always a common representative system for the right and left secondary classes of each subgroup.

Relationship with bipartite graphs: A set by Kőnig in three versions

I.

As Dénes Kőnig explains in his monograph Theory of Finite and Infinite Graphs and BL van der Waerden also notes in his 1927 work, van der Waerden's theorem is equivalent to an early graph-theoretical theorem by Dénes Kőnig, which (in modern formulation) can be specified as follows:

A finite regular bipartite graph always has a - factor . ${\displaystyle 1}$

II

Kőnig first gave a lecture on the above sentence in 1914 at the Paris Congress for Mathematical Philosophy and at the same time pointed out its equivalence with the following sentence:

Every finite - regular bipartite graph ( ) breaks down into factors. ${\displaystyle m}$ ${\displaystyle m\in \mathbb {N} }$ ${\displaystyle m}$   ${\displaystyle 1}$

III

As Kőnig further shows, the last two sentences quoted are in turn equivalent to a sentence he published in 1916, which can be formulated as follows:

If at most edges converge in each node of a finite bipartite graph , then the set of edges can be broken down into classes in such a way that every two adjacent edges always belong to different classes. ${\displaystyle m}$ ${\displaystyle m}$

In other words:

If the maximum degree of a finite bipartite graph is the same , then it can be - edged . ${\displaystyle m}$ ${\displaystyle m}$

However, this means nothing more than the following result:

For a finite bipartite graph, the number of edge coloring and the maximum degree are always identical , i.e.:

${\displaystyle \chi ^{\prime }(G)=\Delta (G)}$  .

See also

• Vizing's theorem

literature

Original work

• Dénes König: About graphs and their application to determinant theory and set theory . In: Mathematical Annals . tape 77 , 1916, pp. 453-465 ( link.springer.com ). MR1511872
• Bartel L. van der Waerden: A theorem about classifications of finite sets . In: Treatises from the Mathematical Seminar of the University of Hamburg . tape 5 , 1927, pp. 185-188 ( link.springer.com ). MR3069474
• GA Miller: On a method due to Galois . In: Quarterly Journal of Mathematics . tape 41 , 1910, pp. 382-384 .

Monographs

• Reinhard Diestel : Graph Theory (=  Graduate Texts in Mathematics . Volume 173 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 ( MR2159259 ).
• Rudolf Halin : Graph Theory I (=  yields of research . Volume 138 ). Wissenschaftliche Buchgesellschaft, Darmstadt 1980, ISBN 3-534-06767-3 ( MR0586234 ).
• Dénes König: Theory of finite and infinite graphs . With a treatise by L. Euler. Ed .: H. Sachs (=  Teubner Archive for Mathematics . Volume 6 ). BSB BG Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4 ( MR0886676 ).

References and comments

1. ↑ ^{a b} Bartel L. van der Waerden: A sentence…. In: Abh. Math. Sem. Univ. Hamburg , 5, pp. 185-188
2. ↑ ^{a b} Dénes König: Theory of finite and infinite graphs. 1986, pp. 171 ff., 176-177
3. ↑ Bartel L. van der Waerden: A theorem about class divisions of finite sets . In: Treatises from the Mathematical Seminar of the University of Hamburg . tape 5 , 1927, pp. 187 ( link.springer.com ).
4. ↑ Dénes König: Theory of finite and infinite graphs. 1986, pp. 171, 176.
5. ↑ As Rudolf Halin notes in his graph theory I (p. 166), the terms “ factor” and “ complete pairing ” coincide for bipartite graphs . ${\displaystyle 1}$
6. ↑ ^{a b} Dénes König: Theory of finite and infinite graphs. 1986, pp. 170-171.
7. ↑ The set of nodes on which the graph and its factors are based is the same, while the factorization breaks the set of edges into subsets . ${\displaystyle m}$ ${\displaystyle m}$
8. ↑ Dénes König: About graphs and their application to determinant theory and set theory. In: Mathematische Annalen , Volume 77, 1916, pp. 453–456
9. ^ Reinhard Diestel: Graph Theory. 2005, p. 119