Premium
An Application of Spanning Trees to k ‐Point Separating Families of Functions
Author(s) -
Clark W. Edwin,
McColm Gregory L.,
Shekhtman Boris
Publication year - 1998
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610798006437
Subject(s) - combinatorics , mathematics , spanning tree , disjoint sets , graph , discrete mathematics , cardinality (data modeling) , disjoint union (topology) , computer science , data mining
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.