On large primitive subsets of $\{1,2,\dots ,2n\}$

Abstract

A subset of $\{1,2,\dots ,2n\}$ is said to be primitive if it does not contain any pair of elements $(u,v)$ such that $u$ is a divisor of $v$. Let $D(n)$ denote the number of primitive subsets of $\{1,2,\dots ,2n\}$ with $n$ elements. Numerical evidence suggests that $D(n)$ is roughly $(1.32{)}^n$. We show that for sufficiently large $n$, $$(\mathrm{1.303...}{)}^n<D(n)<(\mathrm{1.408...}{)}^n$$

5 pages

Cited by in corpus (2)

• Counting primitive subsets and other statistics of the divisor graph of $\{1,2,\dots n\}$
• The counting version of a problem of Erdős