Annals of Combinatorics 4 (2000) 183-194
The Theorem of the k-1 Happy Divorces
Andreas W.M. Dress
FSPM-Strukturbildungsprozesse, University of Bielefeld, D-33501 Bielefeld,
Received July 21, 1999
AMS Subject Classification: 03E05, 15A03, 05B35, 05B25, 52C10, 51E20
Abstract. Given a binary relation
R between the elements of two sets X and Y and a natural
number k, it is shown that there exist k injective maps
if and only if the inequality
holds for every finite subset A of X, provided
is finite for all .
Keywords: Marriage Theorem, Sylvester's Theorem, Bernstein's Theorem, de Bruijn-Erdös Theorem, binary relations, k-relations, bases in infinite-dimensional vector spaces
1. L.M. Batten and A. Beutelspacher, The Theory of Finite Linear Spaces, Cambridge University Press, 1993.
2. N.G. de Bruijn and P. Erdös, On a combinatorial problem, Indag. Math. 10 (1948) 421–423.
3. J.G. Basterfield and L.M. Kelly, A characterization of sets of n points which determine n hyperplanes, Proc. Cambridge Philos. Soc. 64 (1968) 585–588.
4. H. Hanani, On the number of lines and planes determined by d points, Sci. Public. Technion 6 (1955) 58–63.