An Application of Spanning Trees to k ‐Point Separating Families of Functions

A family F of functions from ℝ n to R is k ‐point separating if, for every k ‐subset S of ℝ n , there is a function f ∈F 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 F 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 ℝ n , 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 ⩾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.