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|$?



Maximum size of a union of incomparable chains
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$. 


