On path partitions of the divisor graph
Tom 192 / 2020
Acta Arithmetica 192 (2020), 329-339
MSC: Primary 11N37, 11B75; Secondary 05C38, 05C70.
DOI: 10.4064/aa180711-26-4
Opublikowany online: 25 November 2019
Streszczenie
It is known that the longest simple path in the divisor graph that uses integers 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)}.