Increasing tower of subsets of ${1, ..., k}$

Question

Suppose $k$ is fixed. Consider a set $X$ of subsets of the ground set $\{1, \dots, k \}$, with the following property: there is some ordering of the elements of $X$, as $X = \{ x_1, \dots, x_n \}$, such that the chain of sets $Y_j = \cup_{i=1}^j x_i$ is strictly increasing, i.e. $$ \emptyset \subsetneq Y_1 \subsetneq Y_2 \dots \subsetneq Y_n $$

Note that $X$ cannot contain the empty set. When $k = 2$, the set $X$ can be equal to $\{ \{1 \} \}$, $\{ \{2 \} \}$, $\{ \{1 \}, \{1, 2 \} \}$, $\{ \{2 \}, \{1, 2\} \}$, or $\{ \{1 \}, \{2 \} \}$, or $\{ \{1, 2 \} \}$. But $X$ is not allowed to be $\{ \{1 \}, \{2 \}, \{1, 2\} \}$.

Is there a simpler way of expressing this criterion for the set $X$? (That does not require a reference to an explicit ordering of its elements) Has this type of structure been studied before? For example, how many possibilities are there for $X$?

It appears based on some examples that $X$ can be written in this way iff the set $X$ is linearly independent over $GF(2)^k$ (with the obvious correspondence between subsets of $\{1, ... k \}$ and vectors over $GF(2)^k$. I have some trouble proving this criterion

Answer 1

One can give a generating function for the number $f_n(k)$ of $n$-tuples $(X_1,\dots, X_n)$ of subsets of $\{1,2,\dots,k\}$ such that if $Y_j=X_1\cup X_2\cup \cdots\cup X_j$, then the $Y_j$'s are strictly increasing and $Y_n=\{1,\dots,k\}$. This is a kind of ``labelled'' version of the proposed problem. Let $F_n(x)=\sum_k f_n(k)\frac{x^k}{k!}$. Fix a strictly increasing sequence $\emptyset=Y_0,Y_1, \dots, Y_n=\{1,\dots,k\}$ and set $a_j=\#(Y_j-Y_{j-1})$. Then there is one choice for $X_1$ (namely, $X_1=Y_1$), then $2^{a_1}$ choices for $X_2$ (namely, the union of $Y_2-Y_1$ with any subset of $Y_1$, then $2^{a_1+a_2}$ choices for $Y_3$ (namely, the union of $Y_3-Y_2$ with any subset of $Y_2$), etc. Standard properties of exponential generating functions give $$ F_n(x) = \prod_{j=0}^{n-1} (e^{2^jx}-1). $$ If we don't want the condition $Y_n=\{1,2,\dots,k\}$, simply multiply $F_n(x)$ by $e^x$. The actual question seems much harder to me.

Answer 2

You can construct such all such tower as follows:

First, consider towers where you add exactly one element in each step. In the first step, you have $k$ choices, and in step $i$, you have $(k-i)$ choices. Therefore, $k!$ choices total.

Now, each block of $b_i$ such consecutive step can be "compressed" into a bigger one, so we need to partition the steps in consecutive blocks. So, we get in total $$\sum_{b_1 + b_2 + \dotso + b_k = k} \frac{k!}{b_1!b_2!\dotsc b_k!}$$ where we sum over all integer compositions of $k$. We need to divide by the factorials of the block sizes, since the order in which we add the elements does not matter. Now, the multinomial theorem states that this is exactly $k^k$.

Answer 3

For $k=4$ the sets $\{1,2,3\}$, $\{1,2,4\}$, $\{1,3,4\}$ and $\{2,3,4\}$ are linearly independent as elements of $\mathbb Z_2^4$. However, the chain of $Y_i$ can not be strictly increasing.

In the other direction, linear independence is obvious: if a "sum" of some of the $X_i$ is zero, then every element appears in an even number of them. But there is an element in the $X_i$ for the largest $i$ which is not in any of the others.