التفاصيل البيبلوغرافية
العنوان: |
A Hall-type theorem for triplet set systems based on medians in trees |
المؤلفون: |
Dress, Andreas1 andreas@picb.ac.cn, Steel, Mike2 m.steel@math.canterbury.ac.nz |
المصدر: |
Applied Mathematics Letters. Dec2009, Vol. 22 Issue 12, p1789-1792. 4p. |
مصطلحات موضوعية: |
*SET theory, *TREE graphs, *MEDIAN (Mathematics), *MATHEMATICAL analysis, *EXISTENCE theorems, *MATHEMATICAL functions |
مستخلص: |
Abstract: Given a collection of subsets of a finite set , let . 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 of subsets of there exists an injective (i.e. one-to-one) function with for all if and and only if satisfies the property that for all non-empty subsets of , we have . Here, we show that if the condition is replaced by the stronger condition , then we obtain a characterization of this condition for a collection of 3-element subsets of in terms of the existence of an injective function from to the vertices of a tree whose vertex set includes and which satisfies a certain median condition. We then describe an extension of this result to collections of arbitrary-cardinality subsets of . [Copyright &y& Elsevier] |
قاعدة البيانات: |
Academic Search Index |