
Encyclopaedia of DesignTheory: Topic Essay 
A printable PDF version of this document is available.
Clearly the existence of an SDR imposes conditions on the family of sets: any k sets must between them contain at least k elements (since they must have k distinct representatives). In particular, all the sets must be nonempty. Philip Hall [5] proved that this condition is also sufficient for the existence of an SDR. The result is often called Hall's Marriage Theorem, since it is stated in the following form: given n boys, if any k of the boys between them know at least k girls (for 1<=k<=n), then it is possible to marry each boy to a girl that he knows.
We introduce some notation to state the theorem formally. Given a family (X_{1},...,X_{n}) of sets, for each subset I of {1,...,n} we define
X(I) = Union_{i in I} X_{i}.We say that the family satisfies Hall's condition if X(I) >= I for any subset I of {1,...,n}.
Theorem 1 A family of sets has a SDR if and only if it satisfies Hall's condition.
There are many different proofs of this theorem, so we do not give one here. Note that there is a polynomialtime algorithm which either finds an SDR or shows that one cannot exist by finding a violation of Hall's condition.
det(A) = Sum_{pi in S(n)} sgn(pi) a_{1pi(1)}a_{2pi(2)}...a_{n pi(n)},where S(n) is the symmetric group on {1,...,n}, and sgn is the sign function (taking the value +1 on even permutations and 1 on odd permutations). The permanent is the function defined by the same formula without the sign factor:
per(A) = Sum_{pi in S(n)} a_{1pi(1)}a_{2pi(2)}...a_{n pi(n)},
Somewhat surprisingly, while the determinant can be computed in polynomial time, the easierlooking permanent cannot (so far as we know): its calculation is #Pcomplete.
The connection with SDRs lies in the observation that, if A is the zeroone incidence matrix of a family of n subsets of an nset, then per(A) is the number of SDRs of A: each nonzero term in the permanent arises from a permutation whose list of values (pi(1),...,pi(n)) is a SDR, and every SDR contributes one to the sum.
A matrix A is said to be doubly stochastic if its entries are nonnegative and all row and column sums are equal to 1. The name comes from the fact that the transition matrix of a Markov chain with finitely many states (the matrix whose (i,j) entry is the probability of a transition from state i to state j) is nonnegative and has all row sums equal to 1  such a matrix is called stochastic. A permutation matrix (a zeroone matrix with a single nonzero entry in any row or column) is doubly stochastic, though the corresponding Markov chain is "deterministic".
Theorem 2 Let A be a doubly stochastic matrix. Then
A=x_{1}P_{1} + ... + x_{r}P_{r},where P_{i} are permutation matrices and x_{i} positive real numbers with x_{1}+...+x_{r}=1).
Part 1 is a consequence of Hall's Theorem. If X_{i} is the set of indices of columns having nonzero entries in the ith row, then the entries in the columns indexed by X(I) have sum at least I, since they contain all the nonzero entries in the rows indexed by I; so there are at least I such columns. Hence this family of sets has an SDR, of the form (pi(1),...,pi(n)) for some permutation pi. Then the corresponding term in the permanent is nonzero.
Part 2 is then proved by induction on the number of nonzero elements in the matrix. Given a SDR, we subtract a multiple of the corresponding permutation matrix and rescale to get a doubly stochastic matrix with fewer nonzero entries.
Corollary 3 Let (X_{1},...,X_{n}) be a family of kelement subsets of {1,...,n}, and suppose that each element of {1,...,n} lies in exactly k of these sets. Then the family has an SDR, and indeed has k disjoint SDRs.
The first part follows from the fact that, if A is the incidence matrix of the family, then (1/k)A is doubly stochastic. The second part is proved by induction as above. (Here two SDRs are said to be disjoint if the representatives of any set in the two systems are different.)
An application of this result gives the existence of Youden "squares" , [4]. A block design is a set Omega of plots, with two partitions B and T of Omega (the block and treatment partitions). It is binary if any treatment and any block intersect in at most one plot. A square BIBD is a binary design satisfying the three conditions
Corollary 4 Any square BIBD supports a Youden "square".
For, if we translate the block design into an incidence structure (with the treatments as points and the blocks regarded as sets of points), then a part of the Youden partition is an SDR for the resulting family of sets, and the whole partition is a set of k pairwise disjoint SDRs, whose existence is guaranteed by Corollary 3. Note that the third condition of the definition of a square BIBD is not used in this argument.
Theorem 5. Let A be an n×n doubly stochastic matrix. Then per(A)>=n!/n^{n}, with equality if and only if A=(1/n)J, where J is the all1 matrix.
This shows, for example, that a family of sets satisfying the hypotheses of Corollary 3 has at least n!(k/n)^{n} SDRs. For the number of SDRs is the permanent of A, and so is k^{n} times the permanent of the doubly stochastic matrix (1/k)A.
In the case of a symmetric BIBD, we can do better. The incidence matrix satisfies AA^{T}=(klambda)I+lambda J, from which we find that
det(A)^{2} = det(AA^{T}) = k^{2}(klambda)^{v1}.Thus
per(A) >= det(A) = k(klambda)^{(v1)/2},the first inequality holding since the determinant contains terms of both signs which are all positive in the permanent.
Clearly L(n)<=n^{n2}, since there are at most n choices for the entries in each of the n^{2} cells of the square. This upper bound can be further improved to (n!)^{n}, since each row is a permutation of (1,...,n). Further improvements are possible. What about lower bounds?
Let X_{i}={1,...,n} for i=1,...,n. Then each row of a Latin square of order n is an SDR for the family (X_{1},...,X_{n}); and distinct rows correspond to disjoint transversals. So the counting problem is a special case of those considered in the last section, and we can derive lower bounds as follows.
The ith row is an SDR for the family of sets obtained by omitting from X_{j} the i1 entries already used in the jth column in preceding rows. (This guarantees the disjointness.) The resulting sets satisfy the hypotheses of Corollary 3 with k=ni+1. So the number of choices for the ith row is at least n!((ni+1)/n)^{n}. Multiplying these numbers together for i=1,...,n, we obtain
L(n) >= (n!)^{2n}/n^{n2}.Since n! >= (n/e)^{n}, this gives
L(n)>= (n/e^{2})^{n2},which is not too far from the trivial upper bound (their logarithms are asymptotically equal).
Babai [1] exploited this lower bound to show that, asymptotically, almost all Latin squares have trivial automorphism group. The existence of a nontrivial automorphism reduces the upper bound so drastically that, summed over all possible permutations, the total is much smaller than the lower bound for L(n).