{"id":"arxiv/2604.17613","url":"https://arxiv.org/abs/2604.17613","tags":["math.CO","math.NT"],"score":0,"title":"Forbidden subgraphs in divisor graphs and an Erdős divisibility problem","domain":"math.CO","source":"arxiv","authors":["Damek Davis"],"reviews":0,"subject":"math.CO","summary":"Erdős asked for the largest size $f(n)$ of a subset of $\\{1,\\dots,n\\}$ with no element dividing two others. We show that $f(n)=c_2\\,n+o(n)$ for an effectively computable constant $c_2$, and moreover that the number $q(n)$ of such subsets satisfies $q(n)=β_2^{n+o(n)}$ for a computable constant $β_2$. To prove this, we recast the divisibility constraint as forbidding a certain directed subgraph in the divisor graph on $\\{1,\\dots,n\\}$ and prove a more general result: for any finite family of connected forbidden subgraphs of the divisor graph, both the extremal density and counting rate are…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-19","reactions":{}}