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

Abstract

Given a collection $\C$ of subsets of a finite set $X$, let $\bigcup \C = \cup_{S \in \C}S$. Philip Hall's celebrated theorem \cite{hall} concerning `systems of distinct representatives' tells us that for any collection $\C$ of subsets of $X$ there exists an injective (i.e. one-to-one) function $f: \C \to X$ with $f(S)\in S$ for all $S \in \C$ if and and only if $\C$ satisfies the property that for all non-empty subsets $\C'$ of $\C$ we have $|\bigcup \C'| \geq |\C'|$. Here we show that if the condition $|\bigcup \C'| \geq |\C'|$ is replaced by the stronger condition $|\bigcup \C'| \geq |\C'|+2$, then we obtain a characterization of this condition for a collection of 3-element subsets of $X$ in terms of the existence of an injective function from $\C$ to the vertices of a tree whose vertex set includes $X$ and that satisfies a certain median condition. We then describe an extension of this result to collections of arbitrary-cardinality subsets of $X$.

6 pages, no figures