The Theorem of the k-1 Happy Divorces |
| |
Authors: | AWM Dress |
| |
Institution: | FSPM-Strukturbildungsprozesse, University of Bielefeld, D-33501 Bielefeld, Germany, e-mail: dress@mathematik.uni-bielefeld.de, DE
|
| |
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 f1, f2,...,fk: X \hookrightarrow Y X \hookrightarrow Y with # {f1(x), f2(x),...,fk(x)}=k and (x,f1(x)), (x, f2(x)),...,(x, fk(x)) ? R \# \{f_1(x), f_2(x),...,f_k(x)\}=k \quad{\rm and}\quad (x,f_1(x)), (x, f_2(x)),...,(x, f_k(x)) \in R for all x ? X x \in X if and only if the inequality k ·# A £ ?y ? Y min(k, #{a ? A | (a,y) ? R}) k \cdot \# A \leq \sum_{y \in Y} min(k, \#\{a \in A \mid (a,y) \in R\}) holds for every finite subset A of X, provided {y ? Y | (x,y) ? R} \{y \in Y \mid (x,y) \in R\} is finite for all x ? X 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 ? X 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: | |
本文献已被 SpringerLink 等数据库收录! |
|