1
$\begingroup$

Consider the tree $T$ with the set of its maximal elements (denoted $[T]$) equal to $\prod_{m\leq n} X_m$ for some finite sets $X_0,..., X_n$. Let $p(T)=\{b: b\in \prod_{i\leq m \leq j } X_{m}\text{ for some }i<j\leq n \}$.

$\underline{Definition:}$ We say that $S\subseteq p(T)$ shatters $T$ if $$[T]=\{x\in[T]:(\exists b\in S)\ x\restriction\text{dom}(b)=b\}.$$

Is the following combinatorial inequality true:

$\underline{Conjecture}:$ If $S$ shatters $T$ then $$1\leq\sum_{b\in S}\prod_{m\in\text{dom}(b)}\frac{1}{|X_m|}?$$

Improve this question
$\endgroup$
2
  • $\begingroup$ What does the notation $\Pi_{m\leq n} X_m$ mean for sets $X_m$? $\endgroup$
    – kodlu
    Commented Jun 27, 2018 at 0:22
  • $\begingroup$ @kodlu It is the cartesian product $X_0\times...\times X_n$. Elements are ordered n+1-tuples $(x_0,...,x_n)$ where $x_i\in X_i$ $\endgroup$
    – Horse
    Commented Jun 27, 2018 at 0:47

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .