The theorem of the \(k-1\) happy divorces (Q1575086): Difference between revisions

Let \(R\) be a binary relation between the elements of two sets \(X\) and \(Y\), \(k\) be a natural number. In this note the author shows that there exist \(k\) injective maps \(f_1, f_2,\dots,f_k: X\hookrightarrow Y\) with \(\#\{f_1(x), f_2(x),\dots, f_k(x)\}=k\) and \((x, f_1(x)), (x, f_2(x)),\dots, (x, f_k(x))\in R\) for all \(x\in X\) if and only if the inequality \(k\leq \sum_{y\in Y}\min(k, \#\{a\in A \mid (a, y)\leq R\})\) holds for every finite subset \(A\) of \(X\), provided \(\{y\in Y \mid (x, y)\in R\}\) is finite for all \(x\in X\). This result 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 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 the Bernstein theorem and the marriage theorem is also presented. In the concluding part of the note, applications to bases of infinite-dimensional vector spaces and to incidence relations in finite geometry are considered. The note is inspired by Conway's double sum proof of the de Bruijn-Erdős theorem; see \textit{J. G. Basterfield} and \textit{L. M. Kelly} [Proc. Camb. Philos. Soc. 64, 585-588 (1968; Zbl 0183.49602)].