Premium
A General Criterion for the Existence of Transversals
Author(s) -
Aharoni R.,
NashWilliams C. St J. A.,
Shelah S.
Publication year - 1983
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-47.1.43
Subject(s) - transversal (combinatorics) , mathematics , set (abstract data type) , pure mathematics , combinatorics , mathematical analysis , computer science , programming language
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.