A General Criterion for the Existence of Transversals

1983/07/01 by Ron Aharoni, R. Aharoni, C. St. J. A. Nash‐Williams +3 · 3 citations
Mathematics · Computer Science · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #Limits and Structures in Graph Theory

paper · doi:10.1112/plms/s3-47.1.43

Abstract

We present a necessary and sufficient condition for a family of sets to possess a transversal. Its form follows that of P. Hall's theorem: a family has a transversal if and only if it does not contain one of a set of ‘forbidden’ substructures.

Citations

• On Representatives of Subsets

Cited by

• Transversal Hamilton Paths and Cycles
• Combinatorics of reductions between equivalence relations
• Menger's theorem for infinite graphs

Related

• A theory of q-transversals
• A necessary and sufficient condition for k-transversals
• A Simple Condition for the Existence of Transversals
• A counterexample to conjecture 18.5 in "Geometric Etudes in Combinatorial Mathematics", second edition
• A complex analogue of the Goodman-Pollack-Wenger theorem