8
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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}}$? $\endgroup$
    – Boris Bukh
    Aug 20, 2015 at 17:55
  • $\begingroup$ 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. $\endgroup$
    – user78375
    Aug 20, 2015 at 18:00
  • $\begingroup$ 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? $\endgroup$
    – Boris Bukh
    Aug 20, 2015 at 18:05
  • $\begingroup$ "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)$. $\endgroup$
    – user78375
    Aug 20, 2015 at 18:07
  • $\begingroup$ 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. $\endgroup$
    – user78375
    Aug 20, 2015 at 18:12

4 Answers 4

4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Sep 24, 2015 at 3:31
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – user78375
    Aug 26, 2015 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.