{'fraction_non_alphanumeric': 0.06438283595267526, 'fraction_numerical': 0.012608158220024722, 'mean_word_length': 3.5582743077913714, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A generalized marriage theorem

We consider a set-valued mapping on a simple graph and ask for the existence of a disparate selection. The term disparate is defined in the paper and we present a sufficient and necessary condition for the existence of a disparate selection. This approach generalizes the classical marriage theorem of Hall. We define the disparate kernel of the set-valued mapping and provide calculation methods for the disparate kernel and a disparate selection. Our main theorem is applied to a result of Ryser on the completion of partially prepopulated Latin squares and we derive Hall's marriage theorem.


Introduction
We consider a set-valued mapping defined on a simple graph into a finite set. We ask for the existence of a selection with a specific property which we call disparate. This model generalizes a classical result of P. Hall [14] who considered the case when the domain is a complete graph (compare van Lint and Wilson [23] for a definition of complete graph). Our model includes list coloring problems introduced among others by Erdös et al. [8]. Survey articles on recent results and applications of graph and list coloring problems are due to Formanowicz and Tanaś [11] and Sankar et al. [21].
The main result of this paper is a sufficient and necessary condition for the existence of a disparate selection. This condition is described by the existence of a distributed Hall collection. A Hall collection is a condition which had been investigated by several authors using a different terminology and is known to be necessary for the existence of a disparate selection (see e.g. Hilton and Johnson [17], Cropper [5] or Bobga et al. [2]). The existence of a distributed Hall collection is still necessary for the existence of a disparate selection, but also sufficient.
We introduce the terms disparate, complement mappings and cascades. The definitions and proofs, in particular the definition of the complement mapping, use ideas of Halmos and Vaughan [15] in their proof of the marriage theorem.
Based on this characterization we introduce the disparate kernel of a set-valued mapping. The disparate kernel describes the submapping of all disparate selections of a set-valued mapping. We provide a method for the calculation of the disparate kernel and a method for the calculation of a disparate selection.
Also based on this characterization we introduce a condition on the simple graph, such that the existence of a Hall collection is equivalent to the existence of a disparate selection. From this result we derive a result on prepopulated Latin squares of Ryser [20] and the before mentioned result of P. Hall [14].
Finally in this section we collect some basic terms and notations. The symbol ♯ denotes the number of elements (cardinality) of a finite set. The expression X × Y denotes the cartesian product of X and Y . The set of positive integers is denoted by N.
For the concept of set-valued mappings compare Berge [1]. We do not require F to have nonempty image sets as a general condition. But the assumptions in our lemmas and theorems will imply that F has nonempty image sets.
For a set-valued mapping F : X −→ 2 Y and a given set W ⊂ X we define F (W ) = ∪ x∈W F (x). The restriction of F on a subset W ⊂ X is denoted by F |W . The graph of F is defined by G(F ) = {(x, y) ∈ X × Y | y ∈ F (x)}. A submapping of F is another set-valued mapping F ′ : X −→ 2 Y with the property F ′ (x) ⊂ F (x) for each x ∈ X which is written G(F ′ ) ⊂ G(F ).
A selection for F is a point-valued mapping s : X −→ Y such that s(x) ∈ F (x) for each x ∈ X. Given a submapping F ′ and a selection s of F such that F ′ (x) = {s(x)} we identify s with the mapping F ′ . In this sense F ′ is a point-valued mapping.

Disparate Selections
Let (X, E) be an undirected, simple graph with finite vertex set X and edge set E. Let Y be a finite set and let F : X −→ 2 Y be a set-valued mapping.
Two points (x, y), (x ′ , y ′ ) ∈ X × Y are not disparate if and only if they are identical or y = y ′ and {x, x ′ } ∈ E. We extend the definition of disparate points to disparate sets. Definition 2.2. A set A ⊂ X × Y is called disparate if any two points a, a ′ ∈ A, a = a ′ , are disparate.
We use the concept of disparate sets for the definition of disparate selections. In this paper we ask for the existence of a disparate selection for the set-valued mapping F . The main result describes a condition which is sufficient and necessary for the existence of a disparate selection of F .
In the context of coloring problems (when Y denotes the set of colors) a disparate selection is often called a proper coloring (e.g. van Lint and Wilson [23]). A disparate selection s for F represents a proper coloring of the graph (X, E).
The term "disparate selection" is a generalization of the term "complete system of distinct representatives" of P. Hall [14]. Other authors used the terms "alldifferent" resp. "transversal". The term "alldifferent" is widely used in the theory of constraint satisfaction problems. See Dechter and Rossi [6] for an overview on constraint satisfaction problems and see Hoeve [18] for an overview on alldifferent constraints.

The Complement Mapping
Based on disparate points we define the hull and the complement of a set in X ×Y . The hull and the complement are the basic prerequisites for the definition of the complement mapping.
a and a ′ are not disparate }.

Elementary properties of the hull are
The hull and the complement of any set in X ×Y describe a partition of X × Y .
Proof. The proof follows from Definitions 3.1 and 3.2.
Based on Lemma 3.3 we state elementary properties of the complement.
We obtain more properties of the complement.
Proof. By definition of the complement a ∈ A implies a, b are disparate for each b ∈ compl(A). Again by definition of the complement a ∈ compl(compl(A)) if and only if a, b are disparate for each b ∈ compl(A). This shows the statement.
The following statements are equivalent: we may assume v ∈ A and w ∈ B.
We prove a decomposition lemma. and We introduce the complement mapping F W,Z : X\W −→ 2 Y of F depending on subsets W ⊂ X and Z ⊂ G(F |W ). We define this mapping based on a description of the graph The definition of the complement mapping is illustrated in Fig. 1. In particular, F ∅,∅ = F . F W,Z is a submapping of F |(X\W ) . In general, it can not be guaranteed that F W,Z has nonempty images. There are two main usages of the complement mapping in this paper. The first usage is where W and Z are singletons (compare Lemma 3.7). The second usage is illustrated in Lemma 3.8 and Lemma 4.2.
Lemma 3.7. Let x ∈ X and y ∈ F (x). The following statements are equivalent: Proof. "(i) ⇒ (ii)" Consider s |(X\{x}) and the definition of the complement mapping for each z ∈ X. By definition of the complement mapping s is a disparate selection of F and s(x) = y.

Hall Collections
We introduce Hall collections of F and split the set X into subsets W and X\W . We define submappings of F |W and F |(X\W ) and derive Hall collections of these submappings.
Let A V be a subset of G(F |V ) for each nonempty set V ⊂ X. We call a collection of F , i.e., in a collection of F we associate to each nonempty H |W is a collection of F |W . We derive a second collection from H by H W is a collection of F |(X\W ) . Please note, in the definition H W and also in Definition 4.7 we consider the collection H |W (with sets A V , V ⊂ W ) and sets A W ∪V (where W ∪ V contains W ). We do not consider sets A V where V ⊂ X\W . These definitions reflect ideas used by Halmos and Vaughan [15] in their proof of the marriage theorem. Let ∅} be a collection of F and let W ⊂ X be a nonempty set. In the next step we consider a submapping of F |W and show that H |W is a collection of this submapping. We define a submapping F H W of F |W by We consider the complement mapping F W,G(F H W ) as a submapping of F |(X\W ) and show that H W is a collection of this submapping. Proof. Using the definition of F H W , By definition of the complement mapping At this step we introduce an additional condition on collections and call them Hall collections.
Several authors proposed definitions which are equivalent to Hall collections. Hilton and Johnson [17]) considered the maximum size of a transversal. Cropper [5] considered the size of the largest independent set of vertices and Bobga et al. [2] considered the vertex independence number. These authors observed that their condition is necessary but not sufficient for the existence of a proper coloring.
We consider three examples depicted in Fig. 2. The set X consists in all cases of the vertices {1, 2, 3, 4} and are indicated by circled numbers. The edges are drawn in the graphics. The values of the mapping F are drawn close to the vertices. In all cases we choose W = {1, 3, 4}, which is a generalized critical set of F (compare Definition 6.2).
The most right example is an extraction and relabeling of the Sudoku cells {(1, 1), (2,2), (3,2), (8, 2)} (in the notation (row, column)) of Provan [19, It is immediately clear that H |W is a Hall collection of F |W and that H W is a collection of disparate sets if H is a Hall collection of F . At this moment we do not know if H W is also a Hall collection.
In the last step of this section we implement a condition on H such that H W is a Hall collection.
is a disparate set and using Lemma 3.6 with Z = A∈H |W A yields i.e., H W is a Hall collection.

Cascades
We extend the notation and results of Section 4 to cascades. Let W 0 ⊂ X. For any tuple (W 1 , . . . , . We define the predecessor function by We distinguish two cases, use the definition of cascades and of the complementary tuple. Please note, F (W 1 , . . . , W i ) depends on the Hall collection H, but this dependance is not stated explicitly and we do not define the expressions H(W 1 , . . . , W k ) and F (W 1 , . . . , W k ).
. The statement follows from Lemmas 4.1 and 4.2 and the definitions of (i) Using the induction hypothesis (ii) Using the induction hypothesis and "(i)" (ii) Using the induction hypothesis and "(i)" In the remaining part of this section we consider a property of Hall collections of F .
Using the induction hypothesis and Lemma 4.1, i and the definition of H(W 1 , . . . , W i ) and F (W 1 , . . . , W i ).

Generalized Marriage Theorem
This section contains the main result of this paper. We prove a sufficient and necessary condition on F for the existence of a disparate selection. This theorem is called a generalized marriage theorem and the proof is a generalization of the proof of Halmos and Vaughan [15] of the marriage theorem.
Before we are able to state this theorem we have to introduce the generalized Hall condition in an inductive process. Within this process we define generalized critical sets.
This definition describes the initialization of the generalized Hall condition. By induction hypothesis we defined the generalized Hall condition for sets X ′ with ♯X ′ < ♯X. We need some more definitions before we define the generalized Hall condition for sets X of arbitrary size.
In particular ♯W < ♯X in Definition 6.2 and the generalized Hall condition of the mapping (F {x},{(x,y)} ) |W is defined by induction hypothesis.
Critical sets had been used by Halmos and Vaughan [15] in their proof of the marriage theorem without naming them explicitly. Easterfield [7] used critical sets in an algorithm determining a minimal sum in an n × n-array of real numbers and called them "exactly adjusted". Everett and Whaples [9] proved a generalization of Hall's theorem and called them "perfect". The term "critical" had been introduced by M. Hall [13] and he considered critical blocks. Schrijver [22] called them "tight" sets.
The consideration of critical subsets had been used by Crook [4] and Provan [19] in their description of a strategy solving Sudoku puzzles. Crook used the term "preemptive" set and Provan used the term "pigeon-hole rule".
A generalized critical set W ⊂ X of F is called minimal if there does not exist a subset W ′ ⊂ W , W ′ = W , such that W ′ is a generalized critical set of F . Please note, F admits a primitive generalized critical set if and only if F admits a generalized critical set.
Using the notation of primitive critical cascades we are able to introduce a "distributed"-condition on a Hall collection.  Proof. The proof of this theorem requires several lemmas in both directions, which are collected in the next two sections. The implication

Sufficiency
This section contains the lemmas, which are used in the sufficiency part of the generalized marriage theorem. The results of this section are subsumed in Lemma 7.4. Proof. Let (x, y) ∈ G(F ). Using the assumption, X\{x} is not a generalized critical set of F , i.e., F {x},{(x,y)} satisfies the generalized Hall condition (compare Definition 6.2).
In their proof of the marriage theorem Halmos and Vaughan [15] distinguish the cases where F admits a critical set or not. In our context the case where F does not admit a critical set is treated in Lemma 7.1. The case where F admits a critical set is treated in Lemma 7.3. We need a preparatory lemma.
Proof. (W 1 , W 2 , . . . , W k ) is a cascade in W 0 = X. By assumption W 1 is a minimal generalized critical set of F (W 1 , . . . , W 0 ) = F . Using the assumption and Lemma 5.4, W i is a minimal generalized critical set of F (W 1 , . . . , W i−1 ) = F (W 1 )(W 2 , . . . , W i−1 ) for i = 2, . . . , k.  Proof. We prove the statement by induction on the number ♯X of elements in X. The statement is true for ♯X = 1 (compare Definition 6.1).
Let ♯X > 1. By induction hypothesis the statement is true for subsets X ′ ⊂ X with ♯X ′ < ♯X. We distinguish two cases. Case 1: F does not admit a generalized critical set. Choose (x, y) ∈ G(F ) and apply Lemma 7.1. Since ♯(X\{x}) < ♯X we apply the induction hypothesis and there exists a disparate selection s of F {x},{(x,y)} . The statement follows from Lemma 3.7. Case 2: F admits a generalized critical set. Then F admits a minimal generalized critical set W ⊂ X and we know W = ∅ and W = X. Using Lemma 7.3 there exists a submapping F ′ of F |W such that F ′ satisfies the generalized Hall condition and F W,G(F ′ ) satisfies the generalized Hall condition.
By induction hypothesis there exist disparate selections s 1 of F ′ and s 2 of F W,G(F ′ ) . We define a selection s of F by s |W = s 1 and s |(X\W ) = s 2 . Using Lemma 3.8 with Z = G(F ′ ), s is disparate.
This completes the sufficiency part of the generalized marriage theorem.

Necessity
This section contains the lemmas, which are used in the necessity part of the generalized marriage theorem. The results of this section are subsumed in Lemma 8.7.
Any selection s of F induces a collection of F by We collect some elementary properties of disparate selections and the induced collection H s . ( Proof. The statements "(i)" and "(ii)" are a direct consequence of the definition of H s . Using "(ii)" and since s is a disparate selection G(s |(X\W ) ) ⊂ compl(G(s |W )) = compl( A∈H s |W A). We obtain i.e., "(iii)" and this implies "(iv)".

Lemma 8.3. Let s be a disparate selection of F and let W ⊂ X be a nonempty set. H s is W -distributed.
Proof. Let V ⊂ X\W be a nonempty set. Using Lemma 8.2 "(ii)" Please note, in the proof of Lemma 8.3 we do not require W to be a generalized critical set or a minimal generalized critical set. A disparate selection induces a W -distributed Hall collection for any nonempty set W ⊂ X.  Proof. Let (W c 1 , . . . , W c k ) be the complementary tuple of the cascade (W 1 , . . . , W k ). We prove the statements by induction on i = 1, . . . , k. The statements are true for i = 1. Let 2 ≤ i ≤ k. By induction hypothesis "(ii)", s |pre(i−1) is a disparate selection of F (W 1 , . . . , W i−2 ) and we apply Lemma 8.4

Lemma 8.4. Let s be a disparate selection of F and let
.
We distinguish two cases.

The Disparate Kernel
We introduce a submapping of F called the disparate kernel. This submapping consists of all disparate selections of F . We define the submapping F * of F by for each x ∈ X. We call F * the disparate kernel of F .
A set-valued mapping F admits a disparate selection if and only if F * (x) = ∅ for all (or one) x ∈ X, i.e., the graph G(F ⋆ ) of F ⋆ is nonempty if and only if F admits a disparate selection. In the case when the graph (X, E) is complete, F * had been defined in [10,Section 4] and had been called the alldifferent kernel. We state elementary properties of the disparate kernel.
(ii) Let Q be a submapping of F . Q * is a submapping of F * . (iii) Let Q be a submapping of F and let F * be a submapping of Q.
Proof. Statement "(i)" is true, since each disparate selection of F is also a disparate selection of F * . Statement "(ii)" is true, since each disparate selection of Q is also a disparate selection of F . "(iii)" Using the statements "(i)" and "(ii)" we obtain G(F * ) = G((F * ) * ) ⊂ G(Q * ) ⊂ G(F * ), i.e., equality holds.
If F admits a disparate selection, F * is a disparate mapping and F * (x) = ∅ for each x ∈ X. Each disparate mapping admits a disparate selection.
Lemma 9.4. Let F admit a disparate selection. The mapping F * is the largest disparate submapping of F .
Proof. Using Lemma 9.2 "(i)", F * is a disparate mapping and by definition F * is a submapping of F . Let Q be a disparate submapping of F , let x ∈ X and y ∈ Q(x). There exists a disparate selection s of Q such that s(x) = y. Then s is also a selection of F , i.e., y ∈ F * (x) and Q is a submapping of F * . The basic idea of elimination points is that there is never a disparate selection which goes through an elimination point (x, y) (compare Lemma 3.7). We can eliminate this point from G(F ) and the remaining mapping admits the same disparate selections. The relation of the disparate kernel of F and elimination points of F is described in subsequent statements. Lemma 9.6. Let Q be a submapping of F , let F * be a submapping of Q and let W ⊂ X be a nonempty set.
In particular, Lemma 9.6 shows elim F * (W ) = ∅ for each nonempty set W ⊂ X, i.e., G(F * ) does not contain elimination points.
F can be decomposed into the disparate kernel F ⋆ of F and elimination points.
Proof. W.l.o.g. we may assume ♯X > 1. Using Lemma 9.6, it is enough to show Let (x, y) ∈ G(F )\G(F * ). There does not exist a disparate selection s of F such that s(x) = y. Using Lemma 3.7, F {x},{(x,y)} does not admit a disparate selection. Define W = X\{x} = ∅ and using Theorem 6.7, (x, y) ∈ elim F (W ).
Theorem 9.8. The following statements are equivalent: Proof. This statement follows from Theorem 9.7.
The mapping F * can also be used for a unicity statement of disparate selections. Proof. The equivalence of "(i)" and "(ii)" follows from the definition of F * . Theorem 9.9 can be applied to Sudoku problems which are always uniquely solvable.

Calculation of the disparate Kernel
We describe a method for the calculation of the disparate kernel F * of F . This method terminates after finitely many steps with a description of F * or it indicates that F does not admit a disparate selection. In each cycle of the method the mapping F is reduced by elimination points until there do not exist any more points to eliminate.
Obviously, each elimination set is also a generalized critical set. Simple examples show the converse is not true. In contrast to the definition of generalized critical sets (Definition 6.2) we require (x, y) to be in G(F |(X\W ) ) and not only in (X\W ) × Y . The search for elimination sets is the basic idea in the construction of Calculation Method 1.
2. Choose an elimination set W ⊂ X of F i .
3. If F i does not admit an elimination set. STOP. Otherwise continue.
6. Increase i → i + 1 and continue with Step 2.
Calculation Method 1 can be considered as conceptional, since it does not specify how to find an elimination set W in Step 2. In [10, Section 8] a method to determine an elimination set had been proposed when the graph (X, E) is complete.
The idea of using elimination sets in Calculation Method 1 is also used in strategies solving Sudoku puzzles (compare e.g. Crook [4] or Provan [19]).

Lemma 10.2. Calculation Method 1 terminates after finitely many steps.
Proof. Assume the calculation method does not stop at Step 3. Then elim F i (W ) is nonempty and is contained in G(F i ) for each i. Consequently, ♯G(F i+1 ) < ♯G(F i ) and the method will stop at Step 5, since X and Y are finite sets.
It is not necessary to know in advance if F admits a disparate selection before starting with Calculation Method 1. If F admits a disparate selection Calculation Method 1 stops after finitely many steps with the disparate kernel F * of F . If F does not admit a disparate selection, Calculation Method 1 stops at Step 5 and indicates that F does not admit a disparate selection.
If F admits a unique disparate selection, F * (x) is a singleton for each x ∈ X and the result of Calculation Method 1 is a description of this unique disparate selection. If F admits more than one disparate selection, we have to apply Calculation Method 2, which determines one of several disparate selections.

Calculation of a Disparate Selection
We describe a method for the calculation of a disparate selection s of F . This method makes use of Calculation Method 1 and terminates after finitely many steps with a disparate selection. In each cycle of the method the mapping F is reduced to its disparate kernel and any point in the disparate kernel is selected.
2. Determine the disparate kernel (F i ) * of F i with Calculation Method 1.

If Calculation Method 1 terminates at
Step 5. STOP. Otherwise continue.
Please note, F i+1 is defined on X\{x 1 , . . . , x i } at each step of Calculation Method 2. Also note, by using the complement mapping in Step 6, F i+1 may contain new elimination sets.
Proof. Assume the calculation method does not stop at Step 3. Then i increases and the method will stop at Step 5, since X is a finite set.
Based on Lemma 11.1 we define i max 2 to be the largest index which occurs in Calculation Method 2.

Transitive Problems
We introduce an additional condition on our main model which allows us to simplify the generalized Hall condition and the definition of generalized critical sets.
It is our purpose to find a condition such that the existence of Hall collection characterizes the existence of a disparate selection for transitive problems. We start with a modified definition of critical sets and show the relation to generalized critical sets.
Using the definition of size, F admits a Hall collection if and only if size(G(F |W )) ≥ ♯W for each W ⊂ X.
The next lemma shows that each t-critical set is a generalized critical set. We extend the concept of minimal generalized critical sets to tcritical sets. A t-critical set W ⊂ X of F is called minimal if there does not exist a subset W ′ ⊂ W , W ′ = W , such that W ′ is a t-critical set of F . Lemma 12.5. Let W ⊂ X be a minimal generalized critical set and a t-critical set of F . W is a minimal t-critical set of F .
Proof. This is a consequence of Lemma 12.3.
We introduce a formal description of transitive problems.
Lemma 12.7. Let (X, E) be transitive, let a, a ′ , a ′′ ∈ X × Y such that a, a ′ are not disparate and a ′ , a ′′ are not disparate. a, a ′′ are not disparate.
Proof. Choose a set A ⊂ G(F |W ) such that A is disparate and ♯A = size(G(F |W )). By definition of the complement mapping   Let (X, E) be transitive, let G ⊂ X × Y and let A ⊂ hull(G) be a disparate set such that A\G = ∅. There exists a ∈ A\G and g ∈ G\A such that A\{a} ∪ {g} is a disparate set.
Proof. By assumption there exists a ∈ A\G and this implies a ∈ hull(G). By definition of the hull there exists g ∈ G such that a and g are not disparate, i.e., g ∈ G\A. The set A\{a} is disparate. Let a ′ ∈ A\{a}. Using Lemma 12.7, a ′ and g are disparate.
Using Lemma 12.9 and 12.11 we obtain Proof. We prove the statement by induction on the number ♯X of elements in X. The statement is true for ♯X = 1.
When (X, E) is transitive our main theorem from Section 6 can be simplified.
Theorem 12.14. Let (X, E) be transitive. The following statements are equivalent: (i) F admits a Hall collection.
(ii) F admits a disparate selection.
Proof. The statement follows from Theorem 6.7 and Lemma 12.13 The characterization of Theorem 12.14 also had been obtained by Hilton and Johnson [17] when every block of (X, E) is a clique.
Lemma 12.13 also allows a new characterization of critical sets. We show that a minimal generalized critical set is a minimal t-critical set for transitive problems, i.e., for minimal critical sets the converse of Lemma 12.3 becomes true. Proof. Apply Lemma 12.9.
The condition of Lemma 12.17 is not sufficient for W to be a t-critical set of F , in general.
If W ⊂ X induces a complete subgraph of (X, E) the size function can be replaced by the cardinality.
Lemma 12.18. Let (X, E) be transitive, let W ⊂ X be a nonempty set such that the subgraph of (X, E) induced by W is complete and let A ⊂ W × Y be a disparate set.
Proof. The statement is true if A = ∅ and it is clear that y 1 ), . . . (x k , y k )}. Since A is disparate and the subgraph of (X, E) induced by W is complete, y i = y j for 1 ≤ i, j ≤ k, i = j, i.e., ♯{y 1 , . . . , y k } = k and the statement is proved. Lemma 12.19. Let (X, E) be transitive and let W ⊂ X be a nonempty set such that the subgraph of (X, E) induced by W is complete.

A Theorem of Ryser
We consider a Latin square of size n with values in N = {1, . . . , n} where in the upper left corner a rectangle of r rows and s columns is prepopulated in such a way that the values in each row and each column are distinct. Ryser [20] posed and answered the question if it is possible to extend this partial Latin square to a partial Latin square of size r × n.
We derive a new proof of this result based on Theorem 12.14. M. Hall [12] already proved that a partial Latin square of size r × n can always be completed to a Latin square of size n × n.
We denote by N(v) the number of occurences of a value v ∈ N in the rectangle and R(v) denotes the set of all rows in the rectangle where the value v is not contained in the rectangle. Then N(v) + ♯R(v) = r for each v ∈ N. We define This model is of the type introduced in Section 2 and we show it satisfies the property of Section 12. Proof. Let x, x ′ , x ′′ ∈ X, {x, x ′ } ∈ E, {x ′ , x ′′ } ∈ E and x = x ′′ . By definition of X there exist v, v ′ , v ′′ ∈ N, r ∈ R(v), r ′ ∈ R(v ′ ) and r ′′ ∈ R(v ′′ ) such that x = (v, r), x ′ = (v ′ , r ′ ), x ′′ = (v ′′ , r ′′ ). By definition of E, v = v ′ and v ′ = v ′′ . This shows x ′′ = (v, r ′′ ), r ′′ ∈ R(v) and r = r ′′ , i.e., {x, x ′′ } = {(v, r), (v, r ′′ )} ∈ E.
We identify the extension of the partial Latin square with a disparate selection of the set-valued mapping F . By definition of our model the r × s-rectangle can be extended if and only if F admits a selection s such that s(v, r 1 ) = s(v, r 2 ) for each v ∈ N and r 1 , r 2 ∈ R(v), r 1 = r 2 . By definition of E this is true if and only if s is disparate. The value v is placed in row r and column s(v, r) for each (v, r) ∈ X. Proof. "(i) ⇒ (ii)" Let v ∈ N. We distinguish two cases.  The implication "(i) ⇒ (ii)" of Lemma 13.2 also had been proved by Bobga and Johnson [3] (crediting the proof to Hilton and Johnson [16]). The implication "(ii) ⇒ (i)" can be derived from Ryser's result.
With these preliminaries we are able to derive the result of Ryser [20] from our general result. Proof. Using Lemma 13.1 and 13.2 we can apply Theorem 12.14.

Theorem of Hall
In this section we describe the classical marriage theorem of P. Hall [14] in our terminology. This theorem is part of our model when (X, E) is complete. If (X, E) is complete, (X, E) is transitive and each disparate selection describes a complete system of distinct representatives. Theorem 14.1 (P. Hall [14]). Let (X, E) be complete. The following statements are equivalent: (i) ♯F (W ) ≥ ♯W for each W ⊂ X.
(ii) F admits a disparate selection.
Proof. The statement follows from Theorem 12.14 when (X, E) is complete and Lemma 12.19 "(i)".
If (X, E) is complete, t-critical sets of F can be defined in a manner they had been used by Halmos and Vaughan [15] in their proof of the marriage theorem.