EMBEDDINGS AND THE TRACE OF FINITE SETS

The set U subset of or equal to {0, 1}(n) shatters a set of coordinate s D subset of or equal to {1,..., n} if the restrictions of the member s of U to D contain all members of {0, 1}(\D\) In general a set U shat ters at least \U\ sets (Aharoni and Holzman; Pajor, 1985; Sauer, 1972; Shelah, 1972). We characterize those families which shatter exactly \ U\ sets in a graph-theoretical framework. Our characterization leads t o an O(n\U\(3)) time algorithm to determine whether a family U subset of or equal to {0, 1}(n) has this property or not. (C) 1998 Published by Elsevier Science B.V. All rights reserved.