2025/02/17 by Saias, Eric
#Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)
paper · doi:10.48550/arxiv.2502.12056
The divisor graph is the non oriented graph whose vertices are the positive integers, and edges are the a,b such that a divides b or b divides a. Let F(x,y) be the maximum number of integers<= x belonging in one of y pairwise disjoint simple path of the restriction of the divisor graph to integers <= x. Our main result is the following. There exist two real numbers K >c>0 such that for every x and y with x>=2y>=2 , we have cx / log(x/y) <= F(x,y) <= Kx / log(x/y). It answers a question of Erdös.