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

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 $f_1,\,f_2,\hdots,f_k:X\hookrightarrow Y$ with $\#\{f_1(x),\,f_2(x),\hdots,\break f_k(x)\} =k$ and$(x,\,f_1(x)),\,(x,\,f_2(x)),\hdots,(x,\,f_k(x))\in R$ for all $x\in X$ if and only if the inequality $k\cdot \# A\le \sum_{y\in Y}\min (k,\,\# \{ a\in A\bigm| (a,\,y)\in R\} )$ holds for every finite subset A of X, provided $\{ y\in Y\bigm| (x,\,y)\in R\} $ is finite for all $x\in X$.
       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 $x\in X$ 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) 421423.

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) 585588.

4.  H. Hanani, On the number of lines and planes determined by d points, Sci. Public. Technion 6 (1955) 5863.


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