On path partitions of the divisor graph
Volume 192 / 2020
Acta Arithmetica 192 (2020), 329-339
MSC: Primary 11N37, 11B75; Secondary 05C38, 05C70.
DOI: 10.4064/aa180711-26-4
Published online: 25 November 2019
Abstract
It is known that the longest simple path in the divisor graph that uses integers $\leq N$ is of length $\asymp N/\!\log N$. We study the partitions of $\{1,\dots , N\}$ into a \emph {minimal} number of paths in the divisor graph, and we show that in such a partition, the longest path can have length asymptotically $N^{1-o(1)}$.
