7
$\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$
  • $\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 '15 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$ – user19871987 Aug 20 '15 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 '15 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$ – user19871987 Aug 20 '15 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$ – user19871987 Aug 20 '15 at 18:12
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$
3
$\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$
  • $\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$ – Gerhard Paseman Sep 24 '15 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$
  • $\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$ – user19871987 Aug 26 '15 at 3:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.