In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section[1][2][3]) 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: 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.
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, every collection of k sets must contain in common at least k different elements.
[4]: 29 The following refinement by H. J. Ryser gives lower bounds on the number of such SDRs.
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.
In group theory, given a subgroup H of a group G, a right (respectively left) transversal is a set containing exactly one element from each right (respectively left) coset of H. In this case, the "sets" (cosets) are mutually disjoint, i.e. the cosets form a partition of the group.
As a particular case of the previous example, given a direct product of groups
, then H is a transversal for the cosets of K. In general, since any equivalence relation on an arbitrary set gives rise to a partition, picking any representative from each equivalence class results in a transversal.
Another instance of a partition-based transversal occurs when one considers the equivalence relation known as the (set-theoretic) kernel of a function, defined for a function
induces a one-to-one correspondence between T and the image of f, henceforth denoted by
; furthermore, g can be extended (not necessarily in a unique manner) so that it is defined on the whole codomain of f by picking arbitrary values for g(z) when z is outside the image of f. It is a simple calculation to verify that g thus defined has the property that
acts as a (not necessarily unique) quasi-inverse for f; within semigroup theory this is simply called an inverse.
Note however that for an arbitrary g with the aforementioned property the "dual" equation
To explain the difference in figurative terms, consider a faculty with m departments, where the faculty dean wants to construct a committee of m members, one member per department.
But now, suppose that some faculty members dislike each other and do not agree to sit in the committee together.
In this case, the committee must be an independent transversal, where the underlying graph describes the "dislike" relations.
In the language of category theory, a transversal of a collection of mutually disjoint sets is a section of the quotient map induced by the collection.
The computational complexity of computing all transversals of an input family of sets has been studied, in particular in the framework of enumeration algorithms.