Independent Transversals with Constraints

Our purpose in this note is to solve a problem in transversal theory concerned with marginal elements. We refer the reader to [1] for the basic definitions and theorems of transversal theory, and to [2] for an account of some problems on marginal elements. Throughout, we suppose that all sets considered are finite. Let £ be a set on which there is defined an independence structure 8 with rank function p. Let M be a given subset of £, 31 = (At: 1 < i ^ n) a family of subsets of £, and s a positive integer. In [2; p. 213], we proposed the problem of finding necessary and sufficient conditions for 31 to possess an independent transversal which intersects M in at least s elements. Some special cases of this problem are easily dealt with. In particular, the problem is simple if 8 is the universal structure on E. Also, for any independence structure 8, it has been solved in the special instance when s = p (M) (see, for example, [2]). For arbitrary 8 and s the problem appears to be less tractable, but we offer here a solution for the case s = 1. F o r / c {1,...,«}, ke{\,...,«}, X £ E, we shall write