Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
1  
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 at 9:10
1  
@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 at 9:15
    
OK, thanks for the clarification! –  Florent Foucaud Jul 4 at 9:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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