Maximum size of a union of incomparable chains

Question

The following question was asked on math.stackexchange, where it received no answers.

https://math.stackexchange.com/questions/1392669/maximum-size-of-a-union-of-incomparable-chains

Let $\mathbb{N}^{<\mathbb{N}}$ denote the set of finite sequences of natural numbers (not including the empty sequence). Order this set by $E\preceq F$ if $E$ is an initial segment of $F$. Call a collection $(s_i)_{i=1}^n$ of subsets of $\mathbb{N}^{<\mathbb{N}}$ incomparable if for $1⩽i,j⩽n$ with $i≠j$, no member of $s_i$ is comparable to any member of $s_j$. Given a finite subset $A$ of $\mathbb{N}^{<\mathbb{N}}$, what is a lower estimate on the largest cardinality of a union of incomparable chains in $A$, as a function of the cardinality of $A$? In particular, is there a number $c>0$ so that any finite subset $A$ admits a subset $B$ which is a union of incomparable chains so that $|B|⩾c|A|$?

Answer 1

There is no such $c$. Assume that you have a set with $n$ elements, and maximal $B$ has $k$ elements. Take two copies $C$, $D$ of $A$ with disjoint supports. Add initial segment $1,1,\dots,1$ of length $k$ to all sequences in $C$, $D$ and consider also $k$ sequences consisting of at most $k$ $1$'s. We get $2n+k$ sequences, and can not cover more than $2k$ by incomparable chains. Ratio $k/n$ tends to $0$ when we iterate this process.

It proves that in general we can not cover at most $O(n/\log n)$ elements, where $n=|A|$ (on each step, $k$ is replaced to $2k$ while $n/k$ increases by $1/2$).

I claim that we may always cover by incomparable chains about $n/\log n$ elements. Namely, if we denote by $w=w(A)$ the length of maximal chain and by $t=t(A)$ maximal number of elements in $B$ (which may be covered by incomparable chains), than $w+t\log_2t\geqslant n=|A|$. Prove by induction in $n$, base $n=1$ is clear. Assume that $n=|A|>1$ and the claim holds for sets with less than $n$ sequences. Let $u$ be the shortest sequence in $A$, $A=\{u\}\sqcup \tilde{A}$. If $u$ is initial segment of all elements of $\tilde{A}$, then $w(A)\geqslant w(\tilde{A})+1$, $t(A)\geqslant t(\tilde{A})$, induction works. If not, then partition $A=A_1\sqcup A_2$, where $A_1$ consists of sequences which start from $u$, $A_2$ of all other sequences in $A$. We have $t(A)=t(A_1)+t(A_2)$, $w(A)\geqslant \max(w(A_1),w(A_2))$. Denote $w(A_i)=w_i$, $t(A_i)=t_i$. It suffices to prove $$ \max(w_1,w_2)+(t_1+t_2)\log_2(t_1+t_2)\geqslant w_1+t_1\log_2 t_1+w_2+t_2\log_2t_2\geqslant |A|, $$ where the second inequality follows from induction proposition. But this is clear. If, say, $t_2\leqslant t_1$, we have $t_2\log_2(t_1+t_2)\geqslant t_2\log_2 t_2+t_2\geqslant t_2\log_2 t_2+w_2$.

Answer 2

I don't know if there is any interest in exact small numbers. Probably not, but I worked out a few small numbers, so I will post them as an answer.

The question is about finite trees. For our purposes, a "tree" is just a finite partially ordered set $T$ in which the set of predecessors of any element is a chain. (I see no advantage in representing it concretely as a tree of sequences.) To save typing I will write "size" for "cardinality", and I will call a set $S\subseteq T$ a "quasichain" if the comparability relation is transitive on $S,$ i.e., if $S$ is a "union of incomparable trees".

The question asks, given a number $t,$ what is the greatest number $q$ such that every tree of size $t$ contains a quasichain of size $q$?

It is convenient to look at the inverse problem: given a number $n,$ define $g(n)$ as the maximum possible size of a tree in which every quasichain has size $\le n.$

It is even more convenient to introduce a second variable and define $f(m,n)$ as the maximum possible size of a tree in which every chain has size $\le m$ and every quasichain has size $\le n.$

Clearly, $f(1,n)=n,$ and $m\ge n\implies f(m,n)=f(n,n)=g(n).$ Also, a little consideration will show that, when $2\le m\le n,$ we have $$f(m,n)=\max\{1+f(m-1,n),\ f(m,1)+f(m,n-1),\ f(m,2)+f(m,n-2),\dots,f\left(m,\left\lfloor\frac n2\right\rfloor\right)+f\left(m,\left\lceil\frac n2\right\rceil\right)\}.$$ I used this recurrence to compute the first dozen values of $f(n,n)=g(n)$ by hand, and got:

$$1,3,5,8,10,13,16,20,22,25,28,32$$

The sequence is not in the OEIS.

Answer 3

Here's an example showing that $c\le{1\over 2}$: let $A_n$ be the set of strings $s$ such that

• $\vert s\vert\le n+1$,

• $s(k)=0$ for $k<n$, and

• $s(n)<n+1$.

Then there are two kinds of big subset of $A_n$ which can be written as a union of elementwise-incomparable chains:

• All the elements of length $n+1$ ($n+1$-many chains, each of length 1), or

• the chain of initial segments of some fixed element of length $n+1$ (one chain, of length $n+2$).

Either way, such a $B$ must have about half the elements of $A_n$, at most.

Answer 4

If A is a finite subset of {(1),(1,2),(1,2,3),...} then any two elements are comparable, so the answer to your question (if I've understood it correctly) is that n = 1 is a tight lower bound.