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.

Improve this 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
    Commented Sep 24, 2015 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$
    – Kurisuto Asutora
    Commented Oct 1, 2015 at 12:08

1 Answer 1

Reset to default
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).

Improve this answer
$\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$
    – Kurisuto Asutora
    Commented Oct 1, 2015 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$
    – Kurisuto Asutora
    Commented Oct 6, 2015 at 11:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .