# Maximum size of a union of incomparable chains

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

• I am confused --- do you really mean "... subsets of $\mathbb{N}^{<\mathbb{N}}$", or rather "... elements of $\mathbb{N}^{<\mathbb{N}}$". If it is former, then how do you compare two subsets of $\mathbb{N}^{<\mathbb{N}}$? – Boris Bukh Aug 20 '15 at 17:55
• I mean subsets. The definition of incomparable states that the members of $s_i$ are incomparable to the members of $s_j$ when $i$ and $j$ are distinct. – user78375 Aug 20 '15 at 18:00
• Still confused: An example of a subset of $\mathbb{N}^{<\mathbb{N}}$ is $\{ (1,5,3), (5,5,100)\}$. Another example is $\{(5,5)\}$. Are these comparable according to your definition? – Boris Bukh Aug 20 '15 at 18:05
• "Comparable" is not defined for sets. Only incomparable. The sets you give fail to be incomparable, since $(5,5)$, a member of the second set, is comparable to a member of the first set, $(5,5,100)$, since $(5,5)$ is an initial segment of $(5,5,100)$. – user78375 Aug 20 '15 at 18:07
• To clarify, a collection of sets being incomparable means that if we pick any members of two different sets from that collection, those members are incomparable. – user78375 Aug 20 '15 at 18:12

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

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.

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.

• Alternatively, one could use a slowly branching tree. Let (1) be the root, and for any member s with terminal element n, throw in s concat (2n) and s concat (2n+1). One can tweak the branching rate and other levels to push c to 1/2 or perhaps below. Gerhard "Construction Lovely As A Tree" Paseman, 2015.09.23 – Gerhard Paseman Sep 24 '15 at 3:31

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.

• The question asks for the maximum cardinalitiy of a union of pairwise incomparable chains. By the definition of incomparable collections of sets, any collection consisting of a single set is incomparable. The set you list is a single chain, and can therefore be written as the union of an incomparable collections of chains (namely the collection consisting of a single chain, the whole set). – user78375 Aug 26 '15 at 3:26