{"id":"631fbcd7-7460-4311-967c-b909305c7d1b","arxiv_id":"1908.02407","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In age-biased attachment graphs, the descendant tree of a fixed root has a beta mixture limit for one attachment per vertex and reaches nearly the whole vertex set for multiple attachments, with matching and independent set greedy limits also derived.","lead":"This paper proves almost sure limits for the size of descendant trees in preferential and uniform attachment graphs, and shows that with several attachments per new vertex a fixed early vertex is ancestor of almost the whole graph. It also gives the asymptotic size and convergence rate of greedy matching and independent set algorithms on these models.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's weakest assumption was Lemma 3.3. I traced the argument: the inclusion relies on collapsing decreasing paths in G1; within-block edges become loops in Gm and can be deleted, leaving a strictly decreasing path from the collapsed block to the root. The m^{-1} factor follows because each block has m vertices. The drift computation in Section 3.1 is internally consistent: Lemma 3.2's hypergeometric factorial moments yield (3.9)-(3.10), loop corrections are O(t^{-1}) in expectations and O(t^{-2}) after dividing by t, and the martingale/Q argument is standard. The only genuine weaknesses are in secondary results: Theorem 2.5's loops-allowed PAM matching proof is a sketch, and the abstract slightly overstates what Theorem 2.5 proves (one-sided rate). Neither undermines the descendant-tree theorems, which are the paper's headline. Therefore no change to the reader's CONDITIONAL verdict is needed.","tokens_in":22663,"tokens_out":53153,"duration_ms":501503,"concrete_test":"Implement the Bollobás-Riordan coupling for m=2, δ=0, r=1, simulate to t=10^5, and at every t verify X_{2,0}(t,1) ≥ (1/2) X_{1,0}(2t,2); also check that X_{2,0}(t,1)/t approaches 1. This directly exercises Lemma 3.3 and the claimed convergence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim (Theorems 2.3 and 2.4(ii)) is supported by a complete proof. The assumption flagged by the reader, Lemma 3.3, is valid: in the coupled processes, a decreasing path in G_{1,δ/m} maps to a decreasing path in G_{m,δ} after suppressing within-block loops, so each block containing a G1-descendant is a G_m-descendant; the block-counting bound gives X_{m,δ}(t,r) ≥ m^{-1} X_{1,δ/m}(mt,mr). The drift equations (3.12)-(3.14) are algebraically consistent, the loop corrections enter only at O(t^{-2}) after scaling, and the martingale argument correctly yields p(∞)∈{0,1}; the positive liminf supplied by Lemma 3.3 forces p(∞)=1. The matching theorem proof sketch (Section 5.1, loops-allowed case) is a real but secondary limitation, affecting Theorem 2.5 only.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the δ-version of the preferential attachment model (PAM) and the uniform attachment model (UAM), with m attachments per incoming vertex. For fixed initial vertex r, it analyzes the size X(t) and total degree Y(t) of the descendant tree rooted at r. The main results are: for m=1, the scaled descendant-tree size converges almost surely to a beta mixture in PAM and to a Beta(1,r−1) limit in UAM; for m>1, the scaled size converges almost surely to 1 in both models. The paper also analyzes two online greedy algorithms: one for large matchings and one for large independent sets, giving a.s. convergence rates for the fractions of vertices involved. The proofs use a new martingale for descendant counts, a coupling between PAM with m attachments and PAM with one attachment, and a general drift lemma for processes with unit steps.","tokens_in":22788,"tokens_out":16058,"duration_ms":161312,"significance":"If the main theorems hold, the descendant-tree results are substantial: they show that in the dense-attachment regime every fixed vertex eventually reaches all but o(t) vertices by decreasing paths, and the m=1 beta-mixture limit is a new explicit distributional result. The paper is unusually clean in that the limit laws are derived by explicit moment identifications rather than by fitting parameters; there are no free constants, and the martingale construction is a genuine methodological contribution. The coupling argument in Lemma 3.3 is elegant and reduces the m>1 case to the m=1 case. The greedy-algorithm results are also useful and include explicit a.s. rates. The main weakness is that one of the headline greedy-matching theorems, Theorem 2.5 for the loops-allowed PAM model, is supported only by a proof sketch in place of a complete derivation.","major_comments":[{"comment":"The proof for the loops-allowed PAM model is not complete. After the 'Loops allowed everywhere' paragraph, the argument consists of one displayed product inequality followed by the assertion that (5.5) follows; however, Lemma 4.2 and Lemma 4.3 require a uniform O(t^{-2}) error in the drift, while the loop corrections in (3.7) are only shown to be 1 − O(t^{-1}). A full derivation of the displayed product and of the resulting error term is needed, or the theorem should be explicitly restricted to the no-loops variant. The same proof also invokes Lemma 4.3(a), which is stated without proof; since Theorem 2.5 depends on it, the extension should be proved or referenced.","section":"Section 5.1 (Theorem 2.5)"},{"comment":"The statement of Theorem 2.5 is weaker than the abstract and introductory description suggest. The theorem proves lim_{t→∞} t^α max{0, x(t) − ρ} = 0, i.e., limsup x(t) ≤ ρ, which yields only a lower bound on the size of the greedy matching, not a two-sided limiting fraction. For UAM and for the independent-set algorithm the results are two-sided, but for PAM greedy matching the paper should state clearly that it determines only an asymptotic lower bound on the matching size.","section":"Sections 2.2 and 5.1"}],"minor_comments":[{"comment":"The denominator in the displayed transition probability for the no-loops model is written as 2mt + 2(i−1) + tδ; with this denominator the probabilities over u ∈ [t] do not sum to 1 for i > 1. The formulas in Lemma 3.2 and in (5.4) use the denominator (2m+δ)t + i − 1, so the display should be corrected to avoid ambiguity.","section":"Section 5.1, no-loops model definition"},{"comment":"The asymptotic formula r_m = 1 − m^{-1} log 2 + O(m^{-2}) should be qualified as holding as m → ∞; for small m it is far from the exact root (for example, m=1 gives 1/3 versus the exact value 2/3).","section":"Section 5.2 (Theorem 2.8)"},{"comment":"The notation 'Z_T := 1 + Z_T' is confusing because the same symbol Z_T is reused with a different meaning; a distinct symbol such as Z'_T is preferable.","section":"Section 4, proof of Lemma 4.2"},{"comment":"The assertion 'Clearly G_{t,1} ⊂ G_{t,m}' is a coupling statement: it requires taking one of the m uniform choices at each vertex to define the m=1 process. Making that coupling explicit would improve rigor.","section":"Section 3.2, proof of Theorem 2.4(ii)"},{"comment":"There are corrupted strings in the source text, including 'Pra/suppress lat' in reference [19] and 'T. /suppress Luczak' in reference [24]; these should be cleaned before publication.","section":"References and text"}],"recommendation":"major_revision","confidential_remarks":"The descendant-tree theorems appear correct and are the strongest part of the paper. The greedy matching proof for loops-allowed PAM is the main gap; it is plausibly fixable with a detailed expansion, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is a worthwhile paper. The main new result—for m>1, in both PAM and UAM, the descendant tree rooted at any fixed vertex contains all but o(t) vertices—is proved cleanly, and the m=1 limit laws are genuinely new for the full δ>-1 range. The greedy matching and independent set rate theorems are useful, but one of them is not fully proved as written.\n\nThe descendant tree part is the strongest section. The martingale Mℓ in Lemma 3.1 is an explicit construction that generalizes Pittel's δ=0 argument, and the moment identification for the beta mixture is standard and convincing. For m>1, the coupling Lemma 3.3 is valid: a decreasing path to mr in the collapsed process maps to a decreasing path to r in Gm,δ, so the block-counting bound works. I checked the drift equations (3.12)–(3.14) and they are algebraically consistent; the loop corrections are O(t^{-2}) after scaling, so the p(∞)∈{0,1} dichotomy plus the positive liminf from the coupled m=1 process forces p(∞)=1. That argument holds up.\n\nThe greedy algorithm sections are also mostly solid. Lemma 4.2/4.3 is a workhorse Chernoff/drift lemma that is proved in detail. The UAM matching theorem and both independent set theorems are fully argued. I especially like the two-sided rate in Lemma 4.3(b) using the reflected process—it is clean.\n\nThe soft spot is Theorem 2.5 for PAM greedy matching. The no-loops-except-at-1 case is proved in full, but the loops-allowed case is explicitly called a proof sketch. The missing part is a careful treatment of the loop corrections in (5.4) and the corresponding inequality; the text says 'the rest of the proof remains the same,' which is plausible but not a complete proof. A referee should ask for that to be filled in. Relatedly, the abstract says the paper determines limiting fractions for each model and each greedy algorithm; for PAM matching that is true only modulo the sketch. These are fixable issues, not deep flaws.\n\nThere are also some LaTeX/OCR artifacts in the text (e.g. 'Pra/suppress lat', '/suppress Luczak') that make the references harder to parse, but they don't affect the mathematics.\n\nWho this is for: random graph theorists and anyone working on influence measures or greedy local algorithms on scale-free networks. It deserves peer review. I would take it as a serious referee assignment, and I'd cite it if I worked on preferential attachment.","headline":"A solid, genuinely useful random graph paper: the descendant tree results are new and correct as far as I can see, but the PAM greedy matching theorem has one proof-sketch gap that should be fixed before publication.","tokens_in":23347,"tokens_out":3023,"would_cite":true,"duration_ms":29396,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C07","05C30","05C80","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"With m>1 edges per vertex, both age-biased attachment models make the descendant tree of any fixed vertex contain all but o(t) vertices almost surely; greedy matching and independent set algorithms reach explicit limits with t^{-α} rates.","keywords":["preferential attachment","uniform attachment","age-biased graphs","descendant trees","greedy matching","greedy independent set","factorial martingales","almost sure convergence"],"falsifier":"Run the coupled construction for m=2, δ=0, r=1 and check along many sample paths whether $X_{2,0}(t,1) \\ge \\tfrac12 X_{1,0}(2t,2)$ holds for every t up to $10^7$; any violation refutes Lemma 3.3 and the proof of Theorem 2.3. Equally, simulate PAM with m=2 and δ=0 and see whether $X(t)/t$ is observed to approach 1; a limit strictly below 1 would disprove the theorem.","tokens_in":22437,"feed_emoji":"🌳","tokens_out":12042,"duration_ms":106356,"temperature":0.7,"pith_summary":"The paper asks how much influence a fixed early vertex has in two age-biased growing random graph models, the δ-preferential attachment model (PAM) and the uniform attachment model (UAM), measured by the size of its descendant tree—vertices reachable from that root by decreasing paths. It proves that when each new vertex attaches to a single earlier vertex (m=1), the scaled descendant count converges almost surely to a random limit with an explicit distribution: a mixture of two beta distributions for PAM and the minimum of r−1 independent uniforms for UAM, and in both cases the limit is positive. When each new vertex attaches to m>1 earlier vertices, the conclusion is sharper and, the authors argue, surprising: in both models the scaled descendant count tends to 1 almost surely, so every fixed vertex's descendant tree is giant and eventually contains all but o(t) vertices. The same proof machinery also gives almost-sure convergence rates for online greedy matching and greedy independent set algorithms, with explicit limiting fractions of vertices covered.","feed_headline":"m>1 attachments make descendant trees span almost all vertices","feed_subtitle":"With one attachment the descendant fraction has a random limit; with several it converges to one.","key_machinery":"The argument is carried by a new family of factorial-type martingales built from the descendant count. For m=1 in PAM, the quantity $M_\\ell(t) = (X(t)+\\gamma/(2+\\delta))_{(\\ell)} / (t+\\beta)_{(\\ell)}$, where $(\\cdot)_{(\\ell)}$ is the rising factorial, $\\beta=(1+\\delta)/(2+\\delta)$, and $\\gamma\\in\\{0,-1\\}$ records whether the root looped on itself, is shown to be a martingale; its convergence identifies the $\\beta$-mixture limit. For m>1, the paper transfers the m=1 positivity result through a collapsing coupling that identifies the m-attachment process with a 1-attachment process run at m times the speed, via the inequality $X_{m,\\delta}(t,r)\\ge m^{-1}X_{1,\\delta/m}(mt,mr)$; this converts 'liminf positive' into 'limit equals 1' once the drift equations force the limit into $\\{0,1\\}$. The greedy-algorithm results use a general stochastic-approximation lemma: if the conditional drift of the scaled quantity is a strictly decreasing function h with a unique root, then the process approaches that root with almost-sure rate $t^{-\\alpha}$ for every $\\alpha<1/3$, proved through a Chernoff bound.","core_discovery":"Working in the δ-extension of preferential attachment, where an incoming vertex attaches with probability proportional to degree plus δ, and in the uniform attachment model where it chooses uniformly, the paper's central discovery is a phase transition in the number of attachments m. For m=1, a fixed root r has a descendant tree of size X(t) with X(t)/t converging a.s. to a random variable with a known law, and the law's support is bounded away from zero; for PAM this law is a mixture of two $\\beta$ distributions with parameters $(1,\\frac{r-1}{2+\\delta})$ and $(\\frac{1+\\delta}{2+\\delta}, r)$, weighted by $\\frac{1+\\delta}{(2+\\delta)r-1}$ and $\\frac{(2+\\delta)(r-1)}{(2+\\delta)r-1}$, while for UAM it is the minimum of $r-1$ independent Uniform$[0,1]$ variables. For m>1, almost surely $X(t)/t\\to 1$ and, in PAM, the total degree of the descendant tree $Y(t)/(2mt)\\to 1$; hence all but a vanishing fraction of vertices are descendants of any fixed r. For the greedy matching algorithm, the paper proves that the fraction of unmatched vertices converges a.s. to the root $\\rho_{m,\\delta}$ of a displayed equation in PAM and to the analogous root in UAM, with deviations vanishing faster than $t^{-\\alpha}$ for every $\\alpha<1/3$; the greedy independent set algorithm converges a.s. to the root $w_m$ of $(1-w)^m=w$ in both models, at the same type of rate, with $w_m\\sim(\\log m)/m$ for large m.","pith_inferences":["The m=1 results imply that in single-attachment preferential and uniform attachment, the descendant-tree fraction has a nondegenerate limiting law; the paper does not give the convergence rate for this case, so an editor's inference is that the martingale machinery may yield a $t^{-\\alpha}$-type rate analogous to the greedy algorithms—a testable extension.","Because the m>1 result already covers the UAM limit $\\delta\\to\\infty$, one might expect the same 'giant descendant tree' phenomenon in intermediate preferential-attachment variants with vertex fitness or aging that still admit a similar coupling; testing this would show whether the phenomenon is robust beyond the two models considered.","Since the greedy independent set fraction is $\\sim(\\log m)/m$ and the paper quotes maximum-independent-set upper bounds of $(4+o(1))\\log m/m$ for PAM and $(2+o(1))\\log m/m$ for UAM, an editor's inference is that the greedy algorithm is asymptotically within a constant factor of optimal in both models, though the paper only conjectures the exact constant."],"forward_implications":["In both PAM and UAM with m>1, every fixed vertex's descendant tree eventually contains all but o(t) vertices, so older vertices' decreasing-path influence is nearly total and essentially independent of which vertex is chosen.","The greedy matching algorithm a.s. produces matchings of size at least $(1-\\rho_{m,\\delta})t/2$ in PAM and $(1-\\rho_m)t/2$ in UAM, with the constants explicit roots; for PAM with $\\delta=0$, the matched fraction $r_m=1-\\rho_{m,0}$ increases from 1/2 at m=1 toward 1 as m grows, and $r_2\\approx0.6458$.","The greedy independent set algorithm a.s. produces independent sets of size $w_m t$ in both models, where $w_m\\sim(\\log m)/m$ for large m, and since the set is dominating, this yields small dominating sets of size $\\sim t\\log m/m$.","All these limit statements come with almost-sure convergence rates: after multiplying the deviation by $t^\\alpha$ for any $\\alpha<1/3$, the deviation converges to 0.","For m=1, the explicit beta-mixture and minimum-of-uniforms limit laws identify exactly how the descendant fraction is randomized by the early attachment record, and they guarantee a strictly positive limit almost surely."],"supporting_citations":[{"why":"Introduces the descendant-count X(t) as an influence measure and proves the δ=0 martingale that this paper extends to δ>−1 and to total degree.","marker":"[35]"},{"why":"Provides the rigorous definition of the preferential attachment model used throughout the paper.","marker":"[6]"},{"why":"Establishes the collapsing coupling between m-attachment and 1-attachment preferential attachment processes, the device behind Lemma 3.3.","marker":"[7]"},{"why":"Provides the δ-extension of that coupling and the factorial-product martingale framework for degrees that motivates the new descendant martingale.","marker":"[28]"},{"why":"Constructs factorial-type martingales for individual vertex degrees, the pattern the paper adapts to the global descendant count.","marker":"[29, 30]"},{"why":"Supplies the Chernoff bound used in the stochastic-approximation lemma that yields the $t^{-\\alpha}$ almost-sure rates.","marker":"[24, Theorem 2.8]"},{"why":"Supplies the upper bounds on the largest independent set in these models used to gauge how close the greedy independent set's $\\sim(\\log m)/m$ fraction is to optimal.","marker":"[19]"}],"fun_headline_variants":["Multiple attachments make descendant trees cover almost all vertices","Greedy matching in age-biased graphs: unmatched fraction goes to zero","Independent set greedy algorithm converges to known fraction in both models","One attachment: random tree size; multiple: full tree almost surely","Age-biased attachment: phase transition at m=1 for descendant tree size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole m>1 descendant-tree conclusion rests on a single coupling inequality, that the collapsed tree for m edges contains at least a 1/m fraction of the one-edge tree's vertices; if that fails, the proof that the limit is 1 collapses.","fun_headline_variants_meta":{"raw":{"variants":["Multiple attachments make descendant trees cover almost all vertices","Greedy matching in age-biased graphs: unmatched fraction goes to zero","Independent set greedy algorithm converges to known fraction in both models","One attachment: random tree size; multiple: full tree almost surely","Age-biased attachment: phase transition at m=1 for descendant tree size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00021,"raw_usage":{"total_tokens":1460,"prompt_tokens":1046,"completion_tokens":414,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":325}},"tokens_in":662,"tokens_out":414,"duration_ms":64853,"temperature":1.0,"reasoning_tokens":325,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:45:42.291018+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the coupled construction for m=2, δ=0, r=1 and check along many sample paths whether $X_{2,0}(t,1) \\ge \\tfrac12 X_{1,0}(2t,2)$ holds for every t up to $10^7$; any violation refutes Lemma 3.3 and the proof of Theorem 2.3. Equally, simulate PAM with m=2 and δ=0 and see whether $X(t)/t$ is observed to approach 1; a limit strictly below 1 would disprove the theorem.","supporting_citations":[{"cited_title":"On Bollob\\'as-Riordan random pairing model of preferential attachment graph","cited_arxiv_id":"1811.10764","evidence_quote":"Introduces the descendant-count X(t) as an influence measure and proves the δ=0 martingale that this paper extends to δ>−1 and to total degree."},{"cited_title":"Bollob´ as, O","cited_arxiv_id":null,"evidence_quote":"Provides the rigorous definition of the preferential attachment model used throughout the paper."},{"cited_title":"van der Hofstad, Random Graphs and Complex Networks, V1 , Cambridge University Press (2017)","cited_arxiv_id":null,"evidence_quote":"Provides the δ-extension of that coupling and the factorial-product martingale framework for degrees that motivates the new descendant martingale."},{"cited_title":"Frieze, X","cited_arxiv_id":null,"evidence_quote":"Supplies the upper bounds on the largest independent set in these models used to gauge how close the greedy independent set's $\\sim(\\log m)/m$ fraction is to optimal."}],"review_version":1}