AN APPLICATION OF SPANNING TREES TO k-POINT SEPARATING FAMILIES OF FUNCTIONS

Abstract

A family [Fscr ] of functions from ℝⁿ to ℝ is k-point separating if, for every k-subset S of ℝⁿ, there is a function f∈[Fscr ] such that f is one-to-one on S. The paper shows that, if the functions are required to be linear (or smooth), then a minimum k-point separating family [Fscr ] has cardinality n(k−1). In the linear case, this result is extended to a larger class of fields including all infinite fields as well as some finite fields (depending on k and n). Also, some partial results are obtained for continuous functions on ℝⁿ, including the case when k is infinite. The proof of the main result is based on graph theoretic results that have some interest in their own right. Say that a graph is an n-tree if it is a union of n edge-disjoint spanning trees. It is shown that every graph with k[ges ]2 vertices and n(k−1) edges has a non-trivial subgraph which is an n-tree. A determinantal criterion is also established for a graph with k vertices and n(k−1) edges to be an n-tree.