Skip to main content
1 of 4
kodlu
  • 10.4k
  • 2
  • 36
  • 55

Weighted maximal number of disjoint chains in the integer divisibility poset for $\{1,2,\ldots,n\}$

In the mathoverflow question here the asymptotic growth of antichains in the divisibility poset ${\cal P}_n$ of the set of natural numbers $\{1,\ldots,n\}$ is considered. I have a somewhat dual question.

Consider a ``packing'' of disjoint chains $C_x$ where $$C_x=\{x,y_1 x, y_1 y_2 x, \ldots \} \in \{1,2,\ldots,n\}$$ with $y_i$ natural numbers greater than 1. Thus, $x$ is the minimal element in the chain $C_x$ and $C_{x'}\cap C_x=\emptyset$ whenever $x \neq x'.$ The cost of a chain $C_x$ is simply $f({\cal C}_x)=1/x$ where $x$ is its minimal element. I want to find a collection of disjoint chains ${\cal M}=\{C_{x_1},\ldots,C_{x_m}\}$ which maximizes the cost $$f({\cal M})=\sum_{i=1}^m f(C_{x_i})=\sum_{i=1}^m \frac{1}{x_i}$$ for large $n$.

The disjointness constraint means that if one was considering the infinite divisibility poset over $\mathbb{N}$ and two chains $C_x,C_{x'}$ merged at some minimal element $k>n$, we don't care and still consider them disjoint.

kodlu
  • 10.4k
  • 2
  • 36
  • 55