1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I think that your $f$ is the same as the shatter function unless I misunderstood something. $\endgroup$
    – domotorp
    Jul 2, 2014 at 11:31

0

Your Answer

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

Browse other questions tagged or ask your own question.