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

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

2009-06-23

arxiv.org/abs/0906.4271v1

Mathematics

Combinatorics

6 pages, no figures

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

A Hall-type theorem for triplet set systems based on medians in trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Hall-type theorem for triplet set systems based on medians in trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Hall-type theorem for triplet set systems based on medians in trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-708474