On the largest strongly connected component of randomly oriented divisor graphs

Jihyung Kim; Tristan Phillips

arxiv: 2604.05176 · v1 · submitted 2026-04-06 · 🧮 math.CO · math.NT

On the largest strongly connected component of randomly oriented divisor graphs

Jihyung Kim , Tristan Phillips This is my paper

Pith reviewed 2026-05-10 19:04 UTC · model grok-4.3

classification 🧮 math.CO math.NT

keywords randomly oriented divisor graphsstrongly connected componentsdivisor functionHardy-Ramanujan theoremasymptotic sizegraph orientationnormal order

0 comments

The pith

For any fixed reversal probability between 0 and 1, the expected size of the largest strongly connected component in the randomly oriented divisor graph on numbers up to N is asymptotic to N.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the randomly oriented divisor graph D_ρ(N) on vertices 1 through N by directing each divisibility edge and then flipping its direction independently with probability ρ. It derives a lower bound on the expected size of the largest strongly connected component expressed in terms of the distribution of the divisor function τ(n). An effective quantitative form of the Hardy-Ramanujan theorem on the normal order of log τ(n) then upgrades this lower bound to show that the expectation is asymptotically N whenever ρ is fixed in (0,1). A reader would care because the result demonstrates that random local flips leave the global strong-connectivity structure of the divisor graph essentially intact.

Core claim

The authors prove that E[#Φ(D_ρ(N))] is bounded from below by a quantity that tends to N as N tends to infinity, for each fixed ρ in (0,1). The bound is obtained by relating the existence of large strongly connected components to the typical values of τ(n) and by supplying explicit error terms in the classical normal-order statement for log τ(n).

What carries the argument

The randomly oriented divisor graph D_ρ(N), whose edge directions are chosen independently with reversal probability ρ, together with a lower bound on the size of the largest strongly connected component expressed through the distribution of τ(n).

If this is right

The divisor graph on 1 to N stays essentially strongly connected under any fixed amount of random edge reversal.
Explicit lower bounds on the size of the giant component follow directly from the effective estimates on the normal order of log τ(n).
The same technique yields asymptotic results for the expected size once the distribution of τ(n) is controlled.
The underlying undirected divisor graph supplies enough paths that random reorientations cannot isolate large sets of vertices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same robustness to random orientations may hold for other arithmetic graphs whose connectivity is governed by divisor-like relations.
Numerical checks for moderate N could verify how quickly the proportion approaches 1 as a function of ρ.
The result suggests that strong connectivity in number-theoretic digraphs is stable under local random perturbations, a property that might be tested in related models such as the divisor lattice or the Hasse diagram of the integers.

Load-bearing premise

The lower bound that relates the expected size of the largest strongly connected component to the distribution of τ(n) remains valid and supplies the quantitative estimates needed from the effective Hardy-Ramanujan theorem.

What would settle it

A concrete computation or proof showing that, for some fixed ρ in (0,1), the proportion of vertices lying in the largest strongly connected component stays bounded away from 1 for infinitely many N.

Figures

Figures reproduced from arXiv: 2604.05176 by Jihyung Kim, Tristan Phillips.

**Figure 1.** Figure 1: Oriented divisor graph D5. graph Dρ(5), there are two possibilities for the size of the largest strongly connected component, 1 or 3. The latter case occurs precisely when the triangle with vertices 1, 2, 4 is strongly connected. Finding the expected size of the largest strongly connected component is a straightforward computation: E[#Φ(Dρ(5))] = 3(ρ 2 (1 − ρ) + ρ(1 − ρ) 2 ) + 1(1 − (ρ 2 (1 − ρ) + ρ(1 − ρ… view at source ↗

**Figure 2.** Figure 2: Subgraph of the oriented divisor graph consisting of vertices corresponding to the [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: Average size of largest strongly connected component (SCC) with [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

**Figure 4.** Figure 4: Average size of largest strongly connected component (SCC) for different [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗

**Figure 5.** Figure 5: Average diameter of simulation with ρ = 0.5, together with line of best fit. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗

read the original abstract

We introduce the study of \textit{randomly oriented divisor graphs}. For each $\rho \in [0,1]$, the randomly oriented divisor graph $\mathcal{D}_\rho(N)$ is obtained from the divisor graph on $\{1, 2, \ldots, N\}$ by directing each edge according to divisibility and independently reversing the direction of each edge with probability $\rho$. We study the expected size of the largest strongly connected component, $\textbf{E}[\#\Phi(\mathcal{D}_\rho(N))]$. Our main result gives a lower bound for this quantity in terms of the distribution of values of the divisor function $\tau(n)$. As a consequence, we show that for any fixed $\rho \in (0,1)$, the largest strongly connected component has expected size asymptotic to $N$. To obtain explicit bounds, we prove an effective version of a theorem of Hardy and Ramanujan on the normal order of $\log \tau(n)$, which may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces randomly oriented divisor graphs and proves that for fixed ρ in (0,1) the largest SCC has expected size asymptotic to N, backed by a new effective Hardy-Ramanujan bound on log τ(n).

read the letter

The main point is straightforward: they define the randomly oriented divisor graph D_ρ(N) by taking the usual divisor edges on {1..N} and reversing each independently with probability ρ, then show that the expected size of the largest strongly connected component is asymptotic to N whenever ρ is fixed away from 0 and 1. The argument routes through a lower bound on the number of vertices that can reach many others, expressed in terms of the distribution of τ(n), and they supply an effective quantitative version of the Hardy-Ramanujan normal-order theorem to make the estimates work out explicitly. That effective theorem is the cleanest new piece and looks like it could be lifted for other divisor-function applications. The model itself is simple and natural, and the reduction from connectivity to divisor counts avoids any obvious circularity or parameter fitting. The only real limitation is that everything is stated for fixed ρ; the paper does not address what happens when ρ drifts with N, but that is a separate question. The constants coming out of the effective theorem are probably not optimized for small N, yet the asymptotic claim itself appears to rest on standard tail estimates once the effective bound is in hand. This is squarely for people working in probabilistic combinatorics on arithmetic sets or in analytic number theory who want a concrete random-graph model tied to τ(n). It is technically self-contained enough and introduces enough new material that a serious referee should see it rather than a desk rejection. I would cite the effective Hardy-Ramanujan statement if I needed explicit bounds on the divisor function in a similar setting.

Referee Report

0 major / 3 minor

Summary. The paper introduces randomly oriented divisor graphs D_ρ(N) on the set {1,…,N}, obtained by directing each divisor edge according to divisibility and reversing it independently with probability ρ. It establishes a lower bound on the expected size E[#Φ(D_ρ(N))] of the largest strongly connected component expressed in terms of the distribution of the divisor function τ(n). As a consequence, for every fixed ρ ∈ (0,1) this expectation is shown to be asymptotic to N. The paper also proves an effective version of the Hardy–Ramanujan theorem on the normal order of log τ(n).

Significance. If the central lower bound and the effective theorem hold, the result demonstrates that divisor graphs under random orientation become asymptotically strongly connected for any fixed positive reversal probability, yielding a strong connectivity statement in a number-theoretic random-graph model. The explicit effective form of the Hardy–Ramanujan theorem supplies quantitative estimates that may be of independent use in analytic number theory.

minor comments (3)

[Abstract] The abstract states that the lower bound is given “in terms of the distribution of τ(n)” but does not record the explicit functional form; inserting the precise expression (even in a parenthetical) would improve immediate readability.
[Theorem on normal order of log τ(n)] In the statement of the effective Hardy–Ramanujan theorem, the error term is described as “effective” but the dependence on the parameters is not displayed; adding the explicit O- or o-notation with the implied constants would make the quantitative strength clearer.
[Introduction] Notation Φ(D_ρ(N)) for the largest SCC is introduced without a preceding sentence reminding the reader that Φ denotes the vertex set of that component; a single clarifying sentence in the introduction would prevent any momentary ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for recommending acceptance. No major comments were raised.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives a lower bound on E[#Φ(D_ρ(N))] expressed directly in terms of the distribution of the classical divisor function τ(n), then applies an effective version of the Hardy-Ramanujan theorem on the normal order of log τ(n) that the authors prove independently within the manuscript. Neither step reduces to a self-definition, a fitted parameter renamed as a prediction, nor a load-bearing self-citation; both rest on external number-theoretic facts whose validity is independent of the randomly oriented divisor graph construction. The asymptotic claim for fixed ρ follows from these inputs without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on the known statistical distribution of the divisor function τ(n) together with an effective form of the Hardy-Ramanujan theorem that the authors prove; no free parameters are fitted to the target quantity and no new entities are postulated.

axioms (2)

standard math Standard axioms of probability for independent random edge reversals
Used to define the random orientation process on the divisor graph.
standard math Existence and basic properties of the divisor function τ(n)
Invoked when bounding the size of strongly connected components via the distribution of τ(n).

invented entities (1)

Randomly oriented divisor graph D_ρ(N) no independent evidence
purpose: Model combining divisor relations with independent random edge reversals
Newly introduced object whose connectivity properties are studied; no independent evidence outside the model definition.

pith-pipeline@v0.9.0 · 5463 in / 1362 out tokens · 72595 ms · 2026-05-10T19:04:10.294094+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

[1]

[CGPPS11] Fabienne Castell, Nadine Guillotin-Plantard, Fran¸coise P` ene, and Bruno Schapira

Springer Berlin Heidelberg. [CGPPS11] Fabienne Castell, Nadine Guillotin-Plantard, Fran¸coise P` ene, and Bruno Schapira. A local limit theorem for random walks in random scenery and on randomly oriented lattices.Ann. Probab., 39(6):2079–2118,

work page 2079
[2]

[CMSZ01] Gary Chartrand, Raluca Muntean, Varaporn Saenpholphat, and Ping Zhang. Which graphs are divisor graphs? InProceedings of the Thirty-second South- eastern International Conference on Combinatorics, Graph Theory and Com- puting (Baton Rouge, LA, 2001), volume 151, pages 189–200,

work page 2001
[3]

[HR00] G. H. Hardy and S. Ramanujan. The normal number of prime factors of a numbern[Quart. J. Math.48(1917), 76–92]. InCollected papers of Srinivasa Ramanujan, pages 262–275. AMS Chelsea Publ., Providence, RI,

work page 1917
[4]

On the longest simple path in the divisor graph

[Pom83] Carl Pomerance. On the longest simple path in the divisor graph. InProceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), volume 40, pages 291–304,

work page 1983

[1] [1]

[CGPPS11] Fabienne Castell, Nadine Guillotin-Plantard, Fran¸coise P` ene, and Bruno Schapira

Springer Berlin Heidelberg. [CGPPS11] Fabienne Castell, Nadine Guillotin-Plantard, Fran¸coise P` ene, and Bruno Schapira. A local limit theorem for random walks in random scenery and on randomly oriented lattices.Ann. Probab., 39(6):2079–2118,

work page 2079

[2] [2]

[CMSZ01] Gary Chartrand, Raluca Muntean, Varaporn Saenpholphat, and Ping Zhang. Which graphs are divisor graphs? InProceedings of the Thirty-second South- eastern International Conference on Combinatorics, Graph Theory and Com- puting (Baton Rouge, LA, 2001), volume 151, pages 189–200,

work page 2001

[3] [3]

[HR00] G. H. Hardy and S. Ramanujan. The normal number of prime factors of a numbern[Quart. J. Math.48(1917), 76–92]. InCollected papers of Srinivasa Ramanujan, pages 262–275. AMS Chelsea Publ., Providence, RI,

work page 1917

[4] [4]

On the longest simple path in the divisor graph

[Pom83] Carl Pomerance. On the longest simple path in the divisor graph. InProceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), volume 40, pages 291–304,

work page 1983