Injective choice functions (Q5903315): Difference between revisions

Let \({\mathcal F}=(F_ i;i\in I)\) be a family of subsets of a set S. An injective choice function for \({\mathcal F}\) is a function \(f: I\to S\) such that always \(f(i)\in F_ i\) and f(i)\(\neq f(j)\) if \(i\neq j\). The family \({\mathcal F}\) has a natural representation as a bipartite graph \(\Gamma_{{\mathcal F}}\) on the vertex set \(I\cup S\) (we may suppose I and S are disjoint), with (i,x) joined by an edge if \(x\in F_ i\). An injective choice function of \({\mathcal F}\) corresponds to a matching in \(\Gamma_{{\mathcal F}}\). An injective choice function is often called a marriage for \({\mathcal F}\) (or \(\Gamma_{{\mathcal F}}):\) consider I as a set of men, S as a set of women, with \(F_ i\) the set of women known by man i. An obvious necessary condition for \({\mathcal F}\) to have a marriage is that \(| \cup \{F_ i;i\in K\}| \geq | K|\) for each subset K of I; the classical theorem of P. Hall in 1935 states that if I and each \(F_ i\) are finite then this condition is also sufficient. However, it wasn't until 1983 that a necessary and sufficient condition was found for an arbitrary family to have a marriage, by \textit{R. Aharoni}, \textit{C. St. J. A. Nash-Williams} and \textit{S. Shelah} [Proc. Lond. Math. Soc., III. Ser. 47, 43-68 (1983; Zbl 0522.05002)]. The book under review gives a detailed survey of the various conditions under which a family has a marriage. Full proofs are given for all the results. Chapter 1 reviews basic set theory. A basic notion is that of a critical subfamily: for a subset K of I, the subfamily \({\mathcal F}| K=(F_ i;i\in K)\) is critical if it has a marriage, but ran \(f=\cup \{F_ i;i\in K\}\) for every marriage f of \({\mathcal F}\upharpoonright K\) (so there are no spare women in any marriage of \({\mathcal F}\upharpoonright K)\). Predating the Aharoni, Nash-Williams and Shelah condition were several conditions for the existence of a marriage when the index set I is countable. These are discussed in Chapter 3 of the book. They include the margin functions of \textit{C. St. J. A. Nash-Williams} [J. Comb. Theory, Ser. A 19, 335-366 (1975; Zbl 0311.05003)] and the critical sets condition of \textit{K. Steffens} [J. Comb. Theory, Ser. A 17, 138-144 (1974; Zbl 0284.05002)]. Several sections of this chapter are devoted to critical families, providing several alternative characterizations of critical families. The key idea in the Aharoni, Nash-Williams and Shelah proof is that of a \(\kappa\)-impediment (for regular cardinal \(\kappa)\). Their result is that a family has a marriage if and only if the graph \(\Gamma_{{\mathcal F}}\) contains no \(\kappa\)-impediment (for any \(\kappa)\). Chapter 2 of the book under review is devoted to this result. The authors develop a similar criterion. They say a family \({\mathcal F}\) is \(\lambda\)-positive (for \(\lambda\) a cardinal number) if certain (inductively defined) unmarriable families do not occur as subfamilies of \({\mathcal F}\). They show that a family \({\mathcal F}\) has a marriage if and only if it is \(\lambda\)-positive for all \(\lambda\). (This is based on work of \textit{K. P. Podewski} [Schriftenreihe Inst. Math. Nr. 165, Univ. Hannover (1983)].) They deduce the Aharoni, Nash-Williams and Shelah criterion from this, by showing that \({\mathcal F}\) is not \(\lambda\)-positive (for any \(\lambda)\) if and only if \(\Gamma_{{\mathcal F}}\) contains an impediment. Chapter 2 includes an exposition of the proofs by \textit{R. Aharoni} of König's duality theorem [J. Lond. Math. Soc., II. Ser. 29, 1-12 (1984; Zbl 0505.05049)] and Menger's theorem for graphs with no infinite paths [Eur. J. Comb. 4, 201- 204 (1983; Zbl 0525.05043)].