A Hall-type theorem for triplet set systems based on medians in trees

Given a collection CC of subsets of a finite set XX, let ⋃C=∪S∈CS⋃C=∪S∈CS. Philip Hall’s celebrated theorem [P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26–30] concerning ‘systems of distinct representatives’ tells us that for any collection CC of subsets of XX there exists an injective (i.e. one-to-one) function f:C→Xf:C→X with f(S)∈Sf(S)∈S for all S∈CS∈C if and and only if CC satisfies the property that for all non-empty subsets C′C′ of CC, we have |⋃C′|≥|C||⋃C′|≥|C|. Here, we show that if the condition |⋃C′|≥|C′||⋃C′|≥|C′| is replaced by the stronger condition |⋃C′|≥|C′|+2|⋃C′|≥|C′|+2, then we obtain a characterization of this condition for a collection of 3-element subsets of XX in terms of the existence of an injective function from CC to the vertices of a tree whose vertex set includes XX and which satisfies a certain median condition. We then describe an extension of this result to collections of arbitrary-cardinality subsets of XX.