In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal:
One variation is that there is a bijection f from the transversal to C such that x is an element of f(x) for each x in the transversal. In this case, the transversal is also called a system of distinct representatives (SDR). The other, less commonly used, does not require a one-to-one relation between the elements of the transversal and the sets of C. In this situation, the members of the system of representatives are not necessarily distinct. In computer science, computing transversals is useful in several application domains, with the input family of sets often being described as a hypergraph. In set theory, the axiom of choice is equivalent to the statement that every partition has a transversal.
Existence and number A fundamental question in the study of SDR is whether or not an SDR exists. Hall's marriage theorem gives necessary and sufficient conditions for a finite collection of sets, some possibly overlapping, to have a transversal. The condition is that, for every integer k, the union of any subcollection of k sets must contain at least k unique elements. The following refinement by H. J. Ryser gives lower bounds on the number of such SDRs. Theorem. Let S1, S2, ..., Sm be a collection of sets such that S i 1 ∪ S i 2 ∪ ⋯ ∪ S i k {\displaystyle S_{i_{1}}\cup S_{i_{2}}\cup \dots \cup S_{i_{k}}} contains at least k elements for k = 1,2,...,m and for all k-combinations { i 1 , i 2 , … , i k {\displaystyle i_{1},i_{2},\ldots ,i_{k}} } of the integers 1,2,...,m and suppose that each of these sets contains at least t elements. If t ≤ m then the collection has at least t ! SDRs, and if t > m then the collection has at least t ! / (t - m)! SDRs.
Relation to matching and covering One can construct a bipartite graph in which the vertices on one side are the sets, the vertices on the other side are the elements, and the edges connect a set to the elements it contains. Then, a transversal (defined as a system of distinct representatives) is equivalent to a perfect matching in this graph. One can construct a hypergraph in which the vertices are the elements, and the hyperedges are the sets. Then, a transversal (defined as a system of not-necessarily-distinct representatives) is a vertex cover in a hypergraph.
… excerpt ends here. Continue reading the full article.
