zbMATH — the first resource for mathematics

Concerning Hall’s theorem. (English) Zbl 0852.05012
Bolibruch, A. A. (ed.) et al., Mathematics in St. Petersburg. Based on a three-day conference, St. Petersburg, Russia, October 1993. Providence, RI: American Mathematical Society. Transl., Ser. 2, Am. Math. Soc. 174, 73-77 (1996).
The author begins with a finite version of Hall’s theorem—which deals with a system of distinct representations (SDR) for a family of subsets. An SDR is a set in which each subset in the family contributes one element such that all the elements in the SDR are distinct. P. Hall [J. Lond. Math. Soc. 10, 26-30 (1935; Zbl 0010.34503)] established a necessary and sufficient condition for an SDR to exist. It is not easy to check Hall’s condition explicitly.
This sequel presents an algorithm of polynomial complexity which either produces an SDR or indicates a counterexample to Hall’s condition. The paper does not discuss infinite versions of the theorem—although the theorem remains valid for those cases—but does provide an example from vector space theory and for a class of matrices.
For the entire collection see [Zbl 0836.00020].
Reviewer: R.Scurr (Dunedin)

05A18 Partitions of sets