4
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$ Jul 4, 2014 at 9:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ben Barber
    Jul 4, 2014 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.