Transversal (combinatorics)

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:

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).^[4]^: 29
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.^[5]^: 692^[6]^: 322

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

^ John Mackintosh Howie (1995). Fundamentals of Semigroup Theory. Clarendon Press. p. 63. ISBN 978-0-19-851194-6.
^ Clive Reis (2011). Abstract Algebra: An Introduction to Groups, Rings and Fields. World Scientific. p. 57. ISBN 978-981-4335-64-5.
^ 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.
^ Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
^ Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
^ Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 978-0-13-602040-0
^ John, Bell (December 10, 2021). "The Axiom of Choice". Stanford Encyclopedia of Philosophy. Retrieved December 2, 2024. Let us call Zermelo's 1908 formulation the combinatorial axiom of choice: CAC: Any collection of mutually disjoint nonempty sets has a transversal.

[Howie1995-1] John Mackintosh Howie (1995). Fundamentals of Semigroup Theory. Clarendon Press. p. 63. ISBN 978-0-19-851194-6.

[Reis2011-2] Clive Reis (2011). Abstract Algebra: An Introduction to Groups, Rings and Fields. World Scientific. p. 57. ISBN 978-981-4335-64-5.

[CourcelleEngelfriet2012-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.

[lp-4] Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[5] Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9

[6] Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 978-0-13-602040-0

[7] John, Bell (December 10, 2021). "The Axiom of Choice". Stanford Encyclopedia of Philosophy. Retrieved December 2, 2024. Let us call Zermelo's 1908 formulation the combinatorial axiom of choice: CAC: Any collection of mutually disjoint nonempty sets has a transversal.

[1]

[2]

[3]

[4]

[5]

[6]

[7]