Your requirement 2 can be simply rendered from Q9 that the VC dimension of intersection of hypothesis could not exceed any one of them(hope I got Q9 right)
As for requirement 1, I come up with the case that
H1 := mapping all points to +1
H2 := mapping all points to 1
thus
Quote:
Originally Posted by OlivierB
@marek, Thanks for your contribution.
Let me try and rephrase, not adding much.
.......
For to be true i.e. for H to shatter N, all inequalities must be equalities.
In other words, we must have:
1/ The growth functions of and must be exactly and
2/ Removing the intersection of and from does not decrease the VC dimension of . If the intersection is empty then this condition holds.
If these 2 requirements are not contradictory (which seems plausible but I cannot prove  neither can I visualize with an example), then the VC dimension of is at least .
Now unless there is a mistake in the reasoning, the question is: Can these requirements be met ? Ideally via an example, because beyond the abstract equations, I would really like to 'visualize' a case where these inequalities are 'saturated'.
