7
$\begingroup$

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:

Let $\Phi$ be a collection of subsets of a set $U$, and assume that for all $d$-element subsets $x_1, \dots, x_d$ of $U$ we have $$ \Big| S \cap \{x_1, \dots, x_d\}:~~ S \in \Phi\} \Big| < 2^d. $$ (That means, $\Phi$ is of Vapnik-Chervonenkis dimension at most $d$.)

Then for all $x_1, \dots, x_n \in U$ we have $$ \Big| S \cap \{x_1, \dots, x_n\}:~~S \in \Phi \Big| \leq \sum_{i=0}^d \binom{n}{i} \leq \left( \frac{en}{d} \right)^d. $$

Question: Let $m$ be a fixed positive integer. Assume that $\Phi$ is of VC dimension at most $d$. Let $x_1, \dots, x_n \in U$. Furthermore, let $\mathcal{A}$ denote a family of sets which has the property that

  1. Every set $A \in\mathcal{A}$ is of the form $S \cap \{x_1, \dots, x_n\}$ for some $S \in \Phi$.
  2. For two sets $A_1,A_2$ we have $\big| A_1 \triangle A_2 \big| \geq m.$

What is a good upper bound for the maximal cardinality of $\mathcal{A}$?

In words, what I am looking for is a version of Sauer's lemma under the additional assumption that not all possible sets obtained by intersection are counted, but only those which are "separated" in the sense of the symmetric difference being not too small. (Sauer's lemma is the special case $m=1$.) The application which I have in mind requires $m \approx \varepsilon n$ for some small $\varepsilon$, but I think it is in general an interesting question.

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure I understand the question. ${\mathcal A}\subseteq \{x_1,\dots,x_d\}$ for specific $x_1,\dots,x_d$? in this case, $|A_1\Delta A_2|\leq 2d$. $\endgroup$
    – karpasi
    Sep 24 '15 at 15:56
  • $\begingroup$ Sorry, this was a typo. The condition is "1. Every set $A \in\mathcal{A}$ is of the form $S \cap \{x_1, \dots, x_n\}$ for some $S \in \Phi$." instead of "1. Every set $A \in\mathcal{A}$ is of the form $S \cap \{x_1, \dots, x_d\}$ for some $S \in \Phi$.", In other words, a d should be an n. $\endgroup$ Oct 1 '15 at 12:08
2
+50
$\begingroup$

The following paper by Haussler: http://www.sciencedirect.com/science/article/pii/0097316595900527.

Gives an appropriate upper bound for the case $\mathcal{A} \subset \Phi$. Which results in $|\mathcal{A}| = O((\frac{n}{m+d})^d)$

If i'm not mistaken, you may add to $\Phi$ the set $\{S| \exists A \in \Phi, S \subset A, |S| = d\}$ and it's VC dimensional will not change. If so this gives a bound to your case as well.

For a more modern approach to this packing lemma you can read 5.3 in Matousek, Geometric Discrepancy (http://www.springer.com/us/book/9783540655282).

$\endgroup$
2
  • $\begingroup$ Thank you, this is a very good comment. In my setting $U = [0,1]^d$, the class $\Phi$ consists of axis-parallel boxes in $U$, and the sets $A \in \mathcal{A}$ are point sets in $U$. So $\mathcal{A} \subset \Phi$ is not really satisfied. I have to check whether everything works out, though. $\endgroup$ Oct 1 '15 at 12:14
  • $\begingroup$ Yes, of course your argument works - extactly the way you write in the second part of your comment. Unfortunately Haussler's bound is only better than Sauer's lemma if $m \geq d$, which means that it is of no help for me. However, probably that's all that one can get. Thanks anyway. $\endgroup$ Oct 6 '15 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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