# Is it true that every hypergraph with a large “semi-shattered” set has large VC dimension?

Given a hypergraph $H=(V,E)$ and a set $X\subseteq V$ of vertices, let $int(X)$ be the number of distinct intersections of edges with $X$, i.e. $$int(X)=|\{S\subseteq X, \exists e\in E, e\cap X=S\}|.$$

$X$ is called shattered if $int(X)=2^{|X|}$, i.e. if $int(X)$ reaches its maximum feasible value.

Question: Is the following claim true?

Claim: If $H$ has a set $X$ with $int(X)\geq 2^{|X|}/2$, then $H$ has a shattered set of size at least $|X|/2$.

Remarks:
$\bullet$ The two constants "2" are somewhat arbitrary here, I really want to find out if this claim is true for some pair of (not necessarily equal) constants.
$\bullet$ The claim is true if $|X|\leq 4$ but my proof cannot be extended to higher values.
$\bullet$ My motivation comes from questions related to the Vapnis-Chervonenkis dimension of a hypergraph, i.e. the biggest size of a shattered set.

-

Theorem Let $\mathcal F$ be a family of subsets of $\{1, 2, \ldots, n\}$. If $|\mathcal F| > \binom n 0 + \binom n 1 + \cdots \binom n k$, then $\mathcal F$ shatters a set of size $k+1$.
Note that the inequality is tight, as with equality $\mathcal F$ might not contain any sets of size $k+1$. So the Sauer–Shelah lemma will answer your question whatever constants you use in place of $1/2$.
Excellent, thanks a lot! I see why it works with a constant 2 (because $2^{k}/2>\sum_{i=1}^{k/2}\binom{i}{k}$, but I don't see how to derive such a bound for $2^k/c$: I always get an additional $\log k$-factor... –  Florent Foucaud Jul 4 '14 at 9:10
@FlorentFoucaud, That might not have been the clearest way for me to phrase it. I meant that given $n$, and a family with $\alpha 2^n$ members, then you can work out the best you can hope for using Sauer–Shelah. If $\alpha$ is not $1/2$ then the answer won't be something nice like $\beta 2^n$ (with $\beta$ independent of $n$) because of how the binomial distribution bunches up in the middle. –  Ben Barber Jul 4 '14 at 9:15