Take the 2-minute tour ×

Associated with each family $\mathcal{F}$ of a subsets of a set $\mathbf{X}$ I have a function $f:\mathbb{N}\rightarrow\mathbb{N}$ resembling the dual shatter function. This function obeys a polynomial-exponential dichotomy, and I'm wondering if it's a easy consequence of a known dichotomy.

Let $\mathcal{F}$ be a family of subsets of $\mathbf{X}$. By an $\mathcal{F}$-decision tree I mean a finite complete binary tree whose non-leaves are labelled by subsets in $\mathcal{F}$. If $T$ is an $\mathcal{F}$-decision tree of depth $n$, we associate a subset of $\mathbf{X}$ to each leaf of $T$ as follows.

Suppose $\ell$ is a leaf of $T$ and $X_0,\ X_1,\dots,X_{n-1}$ are the subsets on the root-leaf path above $\ell$. Then associate the set $X_0'\cap X_1' \cap \dots \cap X_{n-1}'$ with $\ell$, where $X_i'$ is $X_i$ if $\ell$ lies to the left of $X_i$ and is the complement $\mathbf{X}- X_i$ otherwise.

Let $F(T)$ be the number of leaves of $T$ whose associated subsets of $\mathbf{X}$ are nonempty. Let $f(n)$ be the maximum of $F(T)$ as $T$ ranges over $\mathcal{F}$-decision trees of depth $n$.

Clearly $f(n)\le 2^n$. I can show that if $f(n)<2^n$ then $f(n)$ grows polynomially. This resembles the dichotomy for the dual shatter function, but as far as I can tell is not implied by it. Is this implied by anything known?

share|improve this question
I think that your $f$ is the same as the shatter function unless I misunderstood something. –  domotorp Jul 2 at 11:31

Your Answer



Browse other questions tagged or ask your own question.