Compressing to VC dimension many points

Any set of labeled examples consistent with some hidden orthogonal rectan-gle can be \compressed " to at most four examples: An upmost, a leftmost, a rightmost and a bottommost positive example. These four examples represent an orthogonal rectangle (the smallest such rectangle that contains them) that is consistent with all examples. Note that the VC dimension of orthogonal rectangles is four and this is exactly the number of examples needed to represent the consistent orthogonal rectangle. A compression scheme of size k for a concept class C picks from any set of examples consistent with some concept in C a subset of up to k examples and this subset represents (via a mapping that that is speci¯c to the class C) a hypothesis consistent with the whole original set of examples. Conjecture: Any concept class of VC dimension d has a compression scheme of size d. What evidence do we have that this conjecture might be true? Call a concept class of VC dimension d maximum if for every subset of m instances, the concept class induces exactly P