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*](http://en.wikipedia.org/wiki/VC_dimension) of a hypergraph, i.e. the biggest size of a shattered set.



Is it true that every hypergraph with a large "semi-shattered" set has large VC dimension?
This follows from the Sauer–Shelah lemma (mentioned in the Wikipedia article on VC-dimension linked in your question).



> 
> **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$.


