Transversal (combinatorics)

In mathematics, given a collection C of sets, 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. One variation, the one that mimics the situation when the sets are mutually disjoint, 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. The other, less commonly used, possibility does not require a one-to-one relation between the elements of the transversal and the sets of C. Loosely speaking, in this situation the members of the system of representatives are not necessarily distinct.^[4][5]

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\times 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 $\operatorname {ker}f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}$. 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 $\operatorname {ker}f$. For a not-necessarily-injective f, fixing a transversal T of $\operatorname {ker}f$ induces a one-to-one correspondence between T and the image of f, henceforth denoted by $\operatorname {Im}f$. Consequently, a function $g:(\operatorname {Im}f)\to T$ is well defined by the property that for all z in $\operatorname {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\circ g\circ 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\circ f\circ g=g$ may not hold. However if we denote by $h=g\circ f\circ g$, then f is a quasi-inverse of h, i.e. $h\circ f\circ 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.^[6]

Theorem. Let S₁, S₂, ..., S_m be a collection of sets such that $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},\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.

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.^[7]

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.

See also

• Axiom of choice
• Permanent

Notes

1. John Mackintosh Howie (1995). Fundamentals of Semigroup Theory. Clarendon Press. p. 63. ISBN 978-0-19-851194-6.
2. Clive Reis (2011). Abstract Algebra: An Introduction to Groups, Rings and Fields. World Scientific. p. 57. ISBN 978-981-4335-64-5.
3. Bruno Courcelle; Joost Engelfriet (2012). Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press. p. 95. ISBN 978-1-139-64400-6.
4. Roberts & Tesman 2009, pg. 692
5. Brualdi 2010, pg. 322
6. Ryser 1963, p. 48
7. Oxley, James G. (2006), Matroid Theory, Oxford graduate texts in mathematics, 3, Oxford University Press, p. 48, ISBN 978-0-19-920250-8.

References

• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 0-13-602040-2
• Lawler, E. L. Combinatorial Optimization: Networks and Matroids. 1976.
• Mirsky, Leon (1971). Transversal Theory: An account of some aspects of combinatorial mathematics. Academic Press. ISBN 0-12-498550-5.
• Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs #14, Mathematical Association of America