Transversal (combinatorics)

Examples

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 G = H × K , 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 f with domain X as the partition of the domain ker ⁡ f := { { y ∈ X ∣ f ( x ) = f ( y ) } ∣ x ∈ X } . which partitions the domain of f into equivalence classes such that all elements in a class map via f to the same value. If f is injective, there is only one transversal of ker ⁡ f . For a not-necessarily-injective f, fixing a transversal T of ker ⁡ f induces a one-to-one correspondence between T and the image of f, henceforth denoted by Im ⁡ f . Consequently, a function g : ( Im ⁡ f ) → T is well defined by the property that for all z in Im ⁡ f , g ( z ) = x where x is the unique element in T such that f ( x ) = z ; 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 f ∘ g ∘ f = f , which is the proof (when the domain and codomain of f are the same set) that the full transformation semigroup is a regular semigroup. g 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 g ∘ f ∘ g = g may not hold. However if we denote by h = g ∘ f ∘ g , then f is a quasi-inverse of h, i.e. h ∘ f ∘ h = h .

Hall's marriage theorem gives necessary and sufficient conditions for a finite collection of not necessarily distinct, but non-empty sets to have a transversal.

Systems of distinct representatives

A refinement, due to H. J. Ryser, of Hall's marriage theorem gives lower bounds on the number of systems of distinct representatives (SDRs) of a collection of sets.

Theorem. Let S₁, S₂, ..., S_m be a collection of sets such that S i 1 ∪ S i 2 ∪ ⋯ ∪ S i k contains at least k elements for k = 1,2,...,m and for all k-combinations { i 1 , i 2 , … , 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.

Generalizations

A partial transversal is a set containing at most one element from each member of the collection, or (in the stricter form of the concept) a set with an injection from the set to C.

The transversals of a finite collection C of finite sets form the basis sets of a matroid, the "transversal matroid" of C. The independent sets of the transversal matroid are the partial transversals of C.

Another generalization of the concept of a transversal would be a set that just has a non-empty intersection with each member of C.

An example of the latter would be a Bernstein set, which is defined as a set that has a non-empty intersection with each set of C, but contains no set of C, where C is the collection of all perfect sets of a topological Polish space. As another example, let C consist of all the lines of a projective plane, then a blocking set in this plane is a set of points which intersects each line but contains no line.

Category theory

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.