Skip to main content
2 of 5
added 443 characters in body
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

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.

Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459