### 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, Germany
dress@mathematik.uni-bielefeld.de

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  with  and for all  if and only if the inequality  holds for every finite subset A of X, provided  is finite for all .
Clearly, as suggested by this paper's title, this implies that, in the context of the celebrated Marriage Theorem, the elements x in X can (simultaneously) marry, get divorced, and remarry again a partner from their favourite list as recorded by R, for altogether k times whenever (a) the list of favoured partners is finite for every  and (b) the above inequalities all hold.
In the course of the argument, a straightforward common generalization of Bernstein's Theorem and the Marriage Theorem will also be presented while applications regarding (i) bases in infinite dimensional vector spaces and (ii) incidence relations in finite geometry (inspired by Conway's double sum proof of the de Bruijn-Erdös Theorem) will conclude the paper.

Keywords: Marriage Theorem, Sylvester's Theorem, Bernstein's Theorem, de Bruijn-Erdös Theorem, binary relations, k-relations, bases in infinite-dimensional vector spaces

References

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.

Get the DVI | PS | PDF file of this abstract.