Counting primitive subsets and other statistics of the divisor graph of \(\{1,2,\dots,n\}\) (Q2225441)

The author proves a formula that allows one to systematically study the rate of growth of certain counting functions in number theory. More precisely, consider the divisor graph, whose vertices are the integers \(\{a,\dots, m\}\) and are linked iff one divides the other. The functions of \((a,m)\) on which the main result applies are those that depend only on the graph-isomorphy class of the connected component of \(a\) in this graph. Many applications are discussed: an alternative proof of the asymptotic number of primitive subsets of integers \(\leq n\) is given, with improved bounds on the exponential rate, and improved second terms; the number of primitive subsets of maximal size is shown to behave similarly. In both cases the exponential rate can be approximated with arbitrary precision. The method is then applied to maximal primitive subsets, and for the median size of primitive subsets -- with the question of proving linear asymptotics in the last case left open. Finally, the number of paths in a minimal path cover, and the size of largest subsets avoiding 3-term geometric progressions, as well as the number of progression-free subsets, are also considered.