{"id":"45bc275d-fe39-42fd-a27c-b18324047813","arxiv_id":"2502.07961","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For preferential attachment graphs with out-degree at least 2 and positive fitness, the distance between two uniformly chosen vertices is asymptotically logν n, with ν the explicit growth parameter of the local limit.","lead":"This paper proves that in preferential attachment networks with out-degree at least two and positive fitness, the typical distance between two random vertices is asymptotically logν n, with an explicit growth rate ν. The result resolves a sharp-bound conjecture and supplies a new technique for analyzing the spectral radius of truncated non-self-adjoint operators.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The constant ν in Theorem 1.1 conflicts with the spectral-radius identity used in Section 4.2: substituting (2.20) into ν = 2/(2χ−1)(cOO+√(cOYcYO)) yields [2m(m+δ)+2√(m(m−1)(m+δ)(m+1+δ))]/δ, not the [2m(m+δ)+√(...)]/δ stated in (1.2).","rationale":"The reader's weakest assumption was that the formula ν = r(Tκ) is imported from [24] and not re-derived here. My stress-test confirms that this external input is load-bearing, but identifies a more specific, internal problem: the proof of Proposition 4.1 writes ν as 2/(2χ−1)(cOO+√(cOYcYO)), which—using the paper's own constants (2.20)—evaluates to a value with a factor 2 in front of the square root, whereas the theorem and Proposition 2.13 state a value without that factor. This makes the sharp constant in the upper-bound proof potentially different from the claimed ν. The discrepancy is purely algebraic and can be settled by direct substitution; it does not require redoing the probabilistic estimates. If the intended ν is the Section 4.2 value, then Theorem 1.1's statement must be corrected; if the intended ν is (1.2), then Proposition 4.1's proof contains an error in the identification of the limiting growth rate. Either way, the paper as currently written does not consistently support the claimed constant. I therefore recommend conditional acceptance pending reconciliation of this constant, rather than rejection, since the main proof architecture may be sound and the issue could be a typographical or notational slip.","tokens_in":92,"tokens_out":40913,"duration_ms":869474,"concrete_test":"Set m=2, δ=1. Compute ν from (1.2): (2·2·3 + √(2·1·3·4))/1 = 12 + √24 ≈ 16.899. Compute the right-hand side of the identity used in Section 4.2: with χ=3/5, 2/(2χ−1)=10, cOO=6/5=1.2, cOY=8/5=1.6, cYO=3/5=0.6, so 10·(1.2+√0.96) ≈ 21.798. If the two values disagree, the proof of Proposition 4.1 proves convergence to a different ν than the one in Theorem 1.1; the authors must reconcile the constant in (1.2), (2.20), and Section 4.2, or the theorem's sharp logarithmic constant is not established by this argument.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The upper bound in Theorem 1.1 is built on Proposition 4.1, whose proof concludes with νζ → ν where ν is taken from the identity in Section 4.2: ν = 2/(2χ−1)(cOO + √(cOYcYO)), with χ = (m+δ)/(2m+δ) and cst given by (2.20). Direct substitution gives 2/(2χ−1) = 2(2m+δ)/δ, cOO = m(m+δ)/(2m+δ), and √(cOYcYO) = √(m(m−1)(m+δ)(m+1+δ))/(2m+δ). The product is therefore [2m(m+δ) + 2√(m(m−1)(m+δ)(m+1+δ))]/δ. This differs from the constant stated in Theorem 1.1, Proposition 2.13, and the abstract, which all give [2m(m+δ) + √(m(m−1)(m+δ)(m+1+δ))]/δ. The two expressions coincide only when the square-root term vanishes, i.e. when m=1, a case excluded by the theorem. Since the first- and second-moment estimates in Sections 5–6 are tuned to the value of ν in Proposition 4.1, either the theorem's constant is wrong or the identity used in the proof is wrong. This is not a criticism of the external result [24] but an internal algebraic mismatch in how it is imported: the proof's limiting growth rate may not be the ν whose logarithm appears in the theorem's denominator.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that in the preferential attachment model PA_n^{(m,δ)}(d) with out-degree m≥2 and fitness δ>0, the graph distance between two uniformly chosen vertices is asymptotically log_ν n in probability, where ν is an explicit constant depending on m and δ. The proof combines a Pólya urn representation with a path-counting technique: a first-moment argument gives the lower bound on typical distances, a conditional second-moment argument gives the upper bound, and a probabilistic, martingale-based proof establishes convergence of the spectral radius of a truncated offspring operator. The paper also extends the main theorem to variants PA_n^{(m,δ)}(a) and PA_n^{(m,δ)}(b) via a collapsing procedure.","tokens_in":76518,"tokens_out":17265,"duration_ms":156323,"significance":"If the result is correct, it resolves a conjecture of the first author and gives the sharp logarithmic order of typical distances in the δ>0 regime of preferential attachment, an open problem since the upper and lower bounds of Dommers–van der Hofstad–Hooghiemstra. The proof strategy is substantial: the path-counting framework is adapted to a model that is not independent, and the convergence of the spectral radius of the non-self-adjoint truncated offspring operator is handled by an isometry and martingale argument rather than by compact perturbation theory. The paper is also transparent about its dependence on the external spectral-radius computation in [24], and the main proof contains no fitted parameters. These strengths are, however, conditional on the internal consistency of the constant ν, which is the main point of concern in this report.","major_comments":[{"comment":"","section":"Section 4.2, paragraph before Eq. (4.19)"},{"comment":"","section":"Appendix E.2, Eq. (E.9)"}],"minor_comments":[{"comment":"","section":"Section 1.3, Eq. (1.2)"},{"comment":"","section":"Section 2.5, item 6"},{"comment":"","section":"Section 4.2, after Eq. (4.30)"}],"recommendation":"major_revision","confidential_remarks":"The mismatch between the theorem's constant ν and the value derived in Section 4.2 is the key blocker. If the formula imported from [24] is correct, the correction is algebraic but global, since the same ν appears throughout the moment estimates. I would not recommend rejection if the authors can align the formulas and re-check the propagation, as the proof architecture appears substantial and otherwise coherent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing you should know: this paper does a lot of real work, but the headline constant is internally inconsistent. In Section 4.2 they state ν = 2/(2χ−1)(cOO + √(cOYcYO)). Plugging in (2.20) gives [2m(m+δ) + 2√(m(m−1)(m+δ)(m+1+δ))]/δ, while Theorem 1.1 and (1.2) state [2m(m+δ) + √(...)]/δ. Those differ by a factor of two on the square-root term. This is not cosmetic: for m=2, δ=1 the two values are roughly 21.8 and 16.9, so the claimed logarithmic base changes numerically. Since the first-moment lower bound and the second-moment upper bound are both calibrated to the ν from Proposition 4.1, the proof as written establishes logarithmic distances with a different constant than the theorem claims. Either the theorem is wrong or the identity in Section 4.2 is wrong; the paper cannot be accepted as is.\n\nThat said, the paper deserves real credit. The path-counting approach via the Pólya urn, the conditional second-moment method, and especially the probabilistic proof of spectral radius convergence under truncation are genuinely novel and carefully executed. If the constant is fixed (checking [24] should settle which expression is correct), this resolves a conjecture left open since [17]/[26]. The lower-bound proof and the good-event estimates look solid, and I saw no circular step or data-fitting.\n\nThe soft spots, in proportion: the constant mismatch is load-bearing and needs to be resolved before anything else. The proof also imports the spectral radius formula from [24] as an external black box, and the case analysis in Sections 5–6 is long and not machine-checked. Those are risks rather than detected errors, but they are why I would not take the theorem on faith even after the constant is corrected.\n\nWho is this for? Specialists in random graphs and preferential attachment. A serious referee should look at it, because the machinery is important and the flaw is identifiable and fixable. My recommendation: send it for peer review, but require the authors to reconcile the two expressions for ν before acceptance.","headline":"The proof is substantial and likely fixable, but the constant ν in Theorem 1.1 disagrees with the spectral-radius identity used in Section 4.2 by a factor of two on the square-root term.","tokens_in":77052,"tokens_out":3338,"would_cite":false,"duration_ms":31350,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60J80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Typical distances in preferential attachment models equal $\\log_\\nu n$ to first order, with $\\nu$ an explicit spectral-radius constant; the paper proves this sharp law in the $\\delta>0$ regime.","keywords":["preferential attachment","typical distance","logarithmic growth","spectral radius","Pólya urn","second-moment method","local weak convergence","small-world networks"],"falsifier":"Numerically compute the spectral radius of the age-truncated offspring operator $T_{\\kappa^\\circ_\\zeta}$ for $m=2$, $\\delta=1$ as $\\zeta\\downarrow 0$. The paper predicts convergence to $\\nu=12+2\\sqrt{6}\\approx 16.899$. A limiting value different from this, or a large-$n$ simulation of $PA^{(2,1)}_n$ whose median distance is not within $o(1)$ of $\\log_{16.899} n$, would refute the claimed constant.","tokens_in":75929,"feed_emoji":"🌐","tokens_out":10285,"duration_ms":88978,"temperature":0.7,"pith_summary":"Preferential attachment models in which each new vertex sends $m\\ge 2$ edges, with positive fitness parameter $\\delta$, are small-world networks: the distance between two uniformly chosen vertices grows like a constant times $\\log n$. This paper identifies the constant exactly. It proves that the graph distance between two uniformly chosen vertices $o_1$ and $o_2$, divided by $\\log_\\nu n$, converges in probability to 1, where $\\nu = \\frac{2m(m+\\delta)+\\sqrt{m(m-1)(m+\\delta)(m+1+\\delta)}}{\\delta}$. Consequently, for every $\\varepsilon>0$ and with probability tending to 1, the distance lies between $(1-\\varepsilon)\\log_\\nu n$ and $(1+\\varepsilon)\\log_\\nu n$. The theorem confirms that typical distances are governed precisely by the exponential growth rate of the local limit's neighborhoods, namely by the spectral radius of the offspring operator.","feed_headline":"Typical distance in preferential attachment is log_ν n, now proved","feed_subtitle":"For m≥2 and δ>0, two uniformly chosen vertices lie at distance (1±ε)log_ν n with high probability.","key_machinery":"The offspring operator $T_\\kappa$ is the integral operator on $L^2([0,1]\\times\\{O,Y\\})$ with kernel $\\kappa((x,s),(y,t))$ given by constants times $(x\\vee y)^{-\\chi}(x\\wedge y)^{-(1-\\chi)}$ when the direction of the edge matches the labels $s,t$, where $\\chi=(m+\\delta)/(2m+\\delta)$. Its iterates count expected numbers of descendants in the Pólya point tree, and its spectral radius is $\\nu$. The proof's workhorse is a truncated kernel $\\kappa^\\circ_\\zeta$ supported on ages in $[3\\zeta,1-\\zeta]$; Proposition 4.1 shows the inner products $\\langle 1, T_{\\kappa^\\circ_\\zeta}^k 1\\rangle$ grow like $(\\nu-o(1))^k$ for small $\\zeta$, via an isometry that turns the inner product into a random-walk probability and a martingale and optional-stopping argument. This transfer from the non-self-adjoint operator to a random walk is what makes the sharp constant accessible.","core_discovery":"The paper's central claim is Theorem 1.1: for every $m\\ge 2$ and $\\delta>0$, if $o_1$ and $o_2$ are independent uniform vertices of $PA_n^{(m,\\delta)}(d)$, then $\\mathrm{dist}(o_1,o_2)/\\log_\\nu n\\to 1$ in probability. The lower bound forbids paths of length at most $(1-\\varepsilon)\\log_\\nu n$ through a first-moment sum over all such paths; the upper bound shows that, with high probability, there is a path of length at most $(1+\\varepsilon)\\log_\\nu n$ connecting the two uniformly chosen vertices, obtained by a conditional second-moment estimate on the number of $k_\\nu^\\star$-step paths between the boundaries of the two $r$-neighborhoods. Every path probability is written as a product over edges, then transformed into products and inner products of the integral kernel $\\kappa$ of the offspring operator. The sharp constant $\\nu$ is the spectral radius of that operator, and the proof is completed by showing that age-truncated versions of the operator have spectral radii converging to $\\nu$.","pith_inferences":["Inference: one natural extension, which the paper states as an open conjecture rather than a proved result, is that the diameter for $\\delta>0$ is also $\\log_\\nu n + O(\\log n)$; the proof here supplies the typical-distance engine but not the extremal control over the few slowly growing vertices.","Inference: the random-walk and martingale route to the truncated spectral radius is likely to be reusable in related models with random out-degree or additive fitness whose local limits have non-self-adjoint offspring operators; the corresponding sharp constant would again be a spectral radius.","Inference: because the proof truncates ages at a growing cutoff, a direct numerical check is available: for small truncations the finite-matrix spectral radii should already be close to $\\nu$, offering a finite-$n$ test of the constant before full simulation."],"forward_implications":["For every $\\varepsilon>0$, the probability that two uniform vertices are joined by a path of length below $(1-\\varepsilon)\\log_\\nu n$ tends to zero, so the spectral radius governs the lower cutoff for distances.","The probability that they fail to be joined by a path of length at most $(1+\\varepsilon)\\log_\\nu n$ also tends to zero, so the typical distance is asymptotically deterministic: $\\mathrm{dist}(o_1,o_2)\\sim \\log_\\nu n$.","The same sharp constant applies to the model variants $PA_n^{(m,\\delta)}(a)$, $(b)$ and $(c)$, which the paper transfers by the collapsing construction.","In the $\\delta>0$ regime the exponent $\\nu$ is finite and larger than 1, placing these models in the small-world class where neighborhoods expand like $\\nu^k$ rather than the ultra-small class where distances grow like $\\log\\log n$."],"supporting_citations":[{"why":"Supplies the exact spectral radius $r(T_\\kappa)=\\nu$ used as the sharp constant in Theorem 1.1.","marker":"[24]"},{"why":"Provides the Pólya urn representation of the model and the marked local convergence to the Pólya point tree, which underpin path probability computations and good-event bounds.","marker":"[23]"},{"why":"Gives the model definitions, the Pólya urn equivalence (Theorem 5.10), and the prior lower bound $\\log_\\nu n$ whose sharpness the paper proves.","marker":"[26]"},{"why":"Supplies the isometry used to rewrite inner products of the truncated kernel as random-walk probabilities.","marker":"[6]"},{"why":"Provides the optional stopping theorem and martingale convergence facts used in the proof of Proposition 4.1.","marker":"[19]"}],"fun_headline_variants":["PA typical distances: log_ν n proven","Preferential attachment: distances are log_ν n","Proof: PA distances scale as log_ν n","log_ν n typical distances in PA, now proven"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exact value of $\\nu$ is imported from a separate theorem about the spectral radius of the offspring operator; if that value were wrong, the logarithmic growth rate might still hold but the asymptotic constant claimed here would be off by a fixed factor.","fun_headline_variants_meta":{"raw":{"variants":["PA typical distances: log_ν n proven","Preferential attachment: distances are log_ν n","Proof: PA distances scale as log_ν n","log_ν n typical distances in PA, now proven"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000173,"raw_usage":{"total_tokens":1237,"prompt_tokens":859,"completion_tokens":378,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":315}},"tokens_in":475,"tokens_out":378,"duration_ms":4452,"temperature":1.0,"reasoning_tokens":315,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:17:41.975796+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically compute the spectral radius of the age-truncated offspring operator $T_{\\kappa^\\circ_\\zeta}$ for $m=2$, $\\delta=1$ as $\\zeta\\downarrow 0$. The paper predicts convergence to $\\nu=12+2\\sqrt{6}\\approx 16.899$. A limiting value different from this, or a large-$n$ simulation of $PA^{(2,1)}_n$ whose median distance is not within $o(1)$ of $\\log_{16.899} n$, would refute the claimed constant.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the model definitions, the Pólya urn equivalence (Theorem 5.10), and the prior lower bound $\\log_\\nu n$ whose sharpness the paper proves."},{"cited_title":"and R IORDAN , O","cited_arxiv_id":null,"evidence_quote":"Supplies the isometry used to rewrite inner products of the truncated kernel as random-walk probabilities."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the optional stopping theorem and martingale convergence facts used in the proof of Proposition 4.1."}],"review_version":1}