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

Abstract

Let $Q(n)$ denote the count of the primitive subsets of the integers $\{1,2\dots n\}$. We give a new proof that $Q(n)={\alpha }^{(1+o(1))n}$ which allows us to give a good error term and to improve upon the lower bound for the value of this constant $\alpha$. We also show that the method developed can be applied to many similar problems that can be stated in terms of the divisor graph, including other questions about primitive sets, geometric-progression-free sets, and the divisor graph path-cover problem.

22 pages. Significantly updated proof improves error terms. Improved bounds on numerical constants