Return to Answer

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\geqslant 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$.

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

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

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\geqslant 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$.

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.

Correct asymptotics is: we may take $|B|\geqslant c n/\log n$, where $n=|A|$. Upper bound is obtained as above. Lower bound may be proved by induction: partition all non-empty sequences in $A$ depending on their first element. Sequences in different classes are incomparable, so our problem is reduced to separate classes. The problem occurs if there is unique class (and possibly empty word). Then proceed with second element and so on.

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