Skip to main content
deleted 1 character in body
Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

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

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

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.

Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

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