Forbidden subgraphs in divisor graphs and an ErdH{o}s divisibility problem
Pith reviewed 2026-05-10 05:14 UTC · model grok-4.3
The pith
For any finite family of connected forbidden subgraphs in the divisor graph, the extremal density and counting rate are effectively computable constants.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper proves that for any finite family of connected forbidden subgraphs of the divisor graph on {1,…,n}, the largest subset avoiding all of them has size equal to c n + o(n) for an effectively computable constant c, and the number of such subsets grows as β^{n + o(n)} for a computable constant β. The argument recasts the divisibility constraint as a forbidden-subgraph condition and invokes McNew's theorem on local statistics of divisor graphs to reduce the global extremal and enumeration questions to finite local optimization.
What carries the argument
forbidding a finite family of connected directed subgraphs in the divisor graph on {1,…,n}
Load-bearing premise
McNew's theorem on local statistics of divisor graphs applies to the extremal and enumeration problems for arbitrary finite families of connected forbidden subgraphs.
What would settle it
A concrete counterexample would be any finite family of connected forbidden subgraphs for which the extremal density cannot be computed by any algorithm, or direct enumeration on small n showing that the predicted constant c fails to match the observed maximum subset sizes.
Figures
read the original abstract
Erd\H{o}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)=\beta_2^{n+o(n)}$ for a computable constant $\beta_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 effectively computable. The proof uses a theorem of McNew on local statistics of divisor graphs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper resolves Erdős's problem on the maximum size f(n) of a subset of {1,...,n} with no element dividing two others by showing f(n) = c_2 n + o(n) for an effectively computable constant c_2. It further shows that the number q(n) of such subsets satisfies q(n) = β_2^{n + o(n)} for a computable β_2. The central contribution is a general theorem: for any finite family F of connected directed forbidden subgraphs in the divisor graph on [n], both the extremal density c_F and the enumeration growth rate β_F are effectively computable. The proof reduces these quantities to an optimization problem over local statistics supplied by McNew's theorem on divisor graphs.
Significance. If the reduction via McNew's theorem holds uniformly, the result supplies the first effective constants for the asymptotic density and counting rate in this family of divisor-graph extremal problems, including the original Erdős question. The effective computability is a notable strength, as it converts an existence result into one where the constants can in principle be approximated to arbitrary precision by finite computation. This framework may extend to other hereditary properties in number-theoretic graphs.
major comments (2)
- [§3] §3 (proof of the general theorem): The reduction to McNew's local statistics must be shown to yield effective computability for arbitrary finite F. Specifically, the manuscript should verify that the local density vectors and their error terms furnished by McNew's theorem remain computable and uniform when F varies over all finite connected families; if the support size or the mixing time in McNew's result depends on F in a non-explicit way, the claimed effective computability of c_F and β_F does not follow directly from a single invocation of the theorem.
- [§4] §4 (application to the Erdős 2-path): The passage from the local statistics to the global density c_2 and growth rate β_2 is presented as an optimization problem, but the manuscript does not exhibit an explicit finite-state automaton or linear program whose optimum equals these constants. Without a concrete description of how the forbidden configuration is encoded into the state space, it is unclear whether the optimization is effective once the local statistics are known.
minor comments (2)
- [§2] The notation for the divisor graph (directed edges from a to b when a divides b) is introduced without an explicit definition of the vertex set and edge direction; a short paragraph in §2 would remove ambiguity for readers unfamiliar with the model.
- [Table 1] Table 1 (numerical approximations of c_2 and β_2) reports values to four decimals but does not state the truncation depth or the precision guarantee derived from McNew's error term; adding this information would strengthen the claim of effective computability.
Simulated Author's Rebuttal
We thank the referee for the careful reading and valuable comments on our manuscript. The points raised concern the details of effective computability in the general theorem and its application. We address each major comment below, indicating the revisions we will incorporate in the next version of the paper.
read point-by-point responses
-
Referee: [§3] §3 (proof of the general theorem): The reduction to McNew's local statistics must be shown to yield effective computability for arbitrary finite F. Specifically, the manuscript should verify that the local density vectors and their error terms furnished by McNew's theorem remain computable and uniform when F varies over all finite connected families; if the support size or the mixing time in McNew's result depends on F in a non-explicit way, the claimed effective computability of c_F and β_F does not follow directly from a single invocation of the theorem.
Authors: We agree that uniformity with respect to F requires explicit verification. McNew's theorem supplies local density vectors and error bounds for the divisor graph that depend only on the window size and are independent of any forbidden family F. For a given finite F consisting of connected directed graphs, the relevant local patterns are those of bounded size (at most the maximum order of graphs in F), so the support is finite and explicitly determined by F. The approximation parameters can therefore be chosen uniformly for that F, reducing the computation of c_F and β_F to a finite-dimensional optimization problem over these vectors. We will revise §3 to include a lemma verifying this uniformity and showing that the resulting constants are computable to any prescribed precision by an algorithm that takes F as input. revision: yes
-
Referee: [§4] §4 (application to the Erdős 2-path): The passage from the local statistics to the global density c_2 and growth rate β_2 is presented as an optimization problem, but the manuscript does not exhibit an explicit finite-state automaton or linear program whose optimum equals these constants. Without a concrete description of how the forbidden configuration is encoded into the state space, it is unclear whether the optimization is effective once the local statistics are known.
Authors: We accept that an explicit encoding would clarify effectiveness. The forbidden 2-path (an element dividing two others) corresponds to excluding local configurations in which a vertex has two outgoing divisibility edges. Given the local statistics from McNew's theorem, the extremal density c_2 is the optimum of a linear program whose variables are the frequencies of admissible local patterns (of size bounded by 3, since the 2-path is small) subject to the marginal constraints supplied by McNew and the exclusion of the forbidden pattern. The growth rate β_2 arises from the largest eigenvalue of the associated transfer matrix on these patterns. We will add to §4 a concrete description of the finite state space (the admissible local directed graphs on at most 3 vertices) together with the explicit linear program and transfer-matrix formulation for the Erdős case. revision: yes
Circularity Check
No circularity detected; central claims rest on external McNew theorem
full rationale
The paper recasts the Erdős divisibility problem as forbidding a directed subgraph in the divisor graph on [n] and invokes McNew's theorem on local statistics of divisor graphs to conclude that the extremal density c_F and counting rate β_F are effectively computable for any finite family F of connected forbidden subgraphs. The abstract and description contain no self-definitional steps, no fitted parameters renamed as predictions, no load-bearing self-citations, and no ansatz or uniqueness results imported from the authors' prior work. The derivation chain is presented as reducing to the external theorem rather than closing on quantities defined inside the paper itself.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption McNew's theorem on local statistics of divisor graphs
Reference graph
Works this paper leans on
- [1]
-
[2]
T. F. Bloom , title =
-
[3]
T. Carroll and D. Galvin and P. Tetali , title =. J. Combin. Theory Ser. A , volume =. 2009 , pages =
work page 2009
- [4]
-
[5]
J. R. Johnson and J. Talbot , title =. J. Combin. Theory Ser. A , volume =. 2010 , pages =
work page 2010
-
[6]
K. Lebensold , title =. Studies in Appl. Math. , volume =. 1976/77 , pages =
work page 1976
- [7]
- [8]
- [9]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.