I should perhaps explain the thinking behind my last post on the general bounds on the variation of growth functions (so someone can check it
). The minimum number of dichotomies on a set of
points where
is given by the fact that we know some set of
points is shattered, and we can extend such a shattering in a minimal way to the whole set of points in a way that excludes all other points. This makes the growth function constant
for all
.
I believe all the possible values of the growth function between this minimum and the bound B(N, k) can occur for some carefully chosen hypothesis set, but haven't actually proved it. Is this so?