@marek, Thanks for your contribution.

Let me try and rephrase, not adding much.

For a hypothesis set H with VD dimension d, we have

The second equality is the result of 2 inequalities in opposite direction. In class, we saw '≤' and '≥' is the subject of problem 2.4 in the book.

Let 2 hypothesis sets

and

with VC dimensions respectively

and

.

We can construct two disjoint

and

putting the intersection of both with one of them only.

The VC dimension of

is

The VC dimension of

is

Let H be the union of these hypothesis sets:

Let

Now in order to try and determine the VC dimension of H, let us compute a higher bound of

:

which we can simplify:

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'.