# 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... Jul 4, 2014 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. Jul 4, 2014 at 9:15