2
$\begingroup$

I "invented" a concept and it feels like it has already been invented before. I would like to know whether such a concept exists and if so, what is its name?


Let $S$ be a family of finite sets.

Say that $S$ is 1-dimensional if there exists a sequence of sets $W_j$, for $j=1,2,\dots$, such that for every $j$:

  • $|W_j|=j$, and
  • For every set $s\in S$, either $s\subseteq W_j$ or $W_j\subseteq s$.

For example:

  • The family of "rays" in $\mathbb{N}$, { {1}; {1,2}; {1,2,3}; ... }, is 1-dimensional. For every $j$, take $W_j=\{1,\dots,j\}$.
  • The family of "squares" in $\mathbb{N}\times \mathbb{N}$, { {(1,1)}; {(1,1),(1,2),(2,1),(2,2)}; {(1,1)...(1,3),(2,1)...(2,3),(3,1)...(3,3)}; ... }, is 1-dimensional. For every $j$, take $W_j$ as a subset of the "square" of side-length $\lceil \sqrt j\rceil $ that contains the "square" of side-length $\lfloor \sqrt j\rfloor$.
  • The family { {1}; {2}; {3}; ... } is not 1-dimensional. No choice for $W_1$, for example, satisfies the definition.

For every integer $d\geq 1$, say that $S$ is $d$-dimensional if there exists a collection of sets $W_{j,t}$, for $j=1,2,\dots$ such that for every $j$:

  • $|W_{j,t}|=j$ for all $t$, and
  • The index $t$ ranges between 1 and $j^{d-1}$ (i.e, there are $j^{d-1}$ subsets for every $j$), and
  • For every set $s\in S$, there exists some $t \in 1,\dots, j^{d-1}$ such that, either $s\subseteq W_{j,t}$ or $W_{j,t}\subseteq s$.

For example:

  • The family of "rectangles" in $\mathbb{N}\times \mathbb{N}$, { {(1,1)}; {(1,1),(1,2)}; {(1,1),(2,1)}; {(1,1),(1,2),(2,1),(2,2)}; ... }, is two-dimensional. For every $j$ and for every $t\in\{1,\dots,j\}$, Take $W_{j,t}$ as a subset of the "rectangle" of length $t$ and height $\lceil j/t \rceil$, which contains the "rectangle" of length $t$ and height $\lfloor j/t \rfloor$.
  • Similarly, the family of "boxes" in $\mathbb{N}^d$ is probably $d$-dimensional.

I am mainly interested in questions such as: how to characterize / identify $d$-dimensional families; what other interesting $d$-dimensional families exist?

EDIT: The motivation to this definition comes from probability. Let $X$ be a random variable whose possible values are sets from the family $S$. I would like to prove claims such as "If the size of $X$ is at least $j$, then it must contain one of the (deterministic) subsets $W_{j,t}$".

EDIT 2: I now found out that what I called "1-dimensional family" is actually called: Filtration.

So, my question becomes: is there a natural extension of filtration to two or more dimensions (as explained above)?

$\endgroup$

1 Answer 1

3
$\begingroup$

The notion that you are describing is somewhat related to the notion of the order dimension of a poset, a notion that has been studied in many papers.

The order dimension of a poset $(X,\leq)$ is the smallest (in many cases) cardinal $\mu$ such that there exists a set $I$ with $|I|=\mu$ and a family of linear orders $(\preceq_{i})_{i\in I}$ such that $\leq$ is equal to $\bigcap_{i\in I}\preceq_{i}$.

Equivalently, the order dimension of a poset $(X,\leq)$ is the smallest cardinal $\mu$ such that there is some set $I$ with $|I|=\mu$ and linear orders $(X_{i})_{i\in I}$ such that $(X,\leq)$ is isomorphic to a subposet of $\prod_{i\in I}(X_{i},\leq)$ with the pointwise ordering.

$\endgroup$

Your Answer

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

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