Pith. sign in

REVIEW 2 major objections 5 minor 35 references

Giant descendant trees, matchings and independent sets in the age-biased attachment graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.02407 v2 pith:KEZSEQOQ submitted 2019-08-07 math.CO

Huseyin Acan , Alan Frieze , Boris Pittel This is my paper · ORCID
classification math.CO MSC 05C0505C0705C3005C8060C05
keywords preferentialattachmentuniformage-biasedgraphsdescendanttreesgreedymatchingindependentsetfactorialmartingalesalmostsureconvergence
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Section 5.1 (Theorem 2.5)] 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.
  2. [Sections 2.2 and 5.1] 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.
minor comments (5)
  1. [Section 5.1, no-loops model definition] 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.
  2. [Section 5.2 (Theorem 2.8)] 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).
  3. [Section 4, proof of Lemma 4.2] 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.
  4. [Section 3.2, proof of Theorem 2.4(ii)] 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.
  5. [References and text] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the main theorems are derived from transition probabilities by self-contained martingale and coupling arguments.

full rationale

The derivation chain is self-contained. Theorem 2.2 starts from the transition probabilities (2.2), reduces the one-step increment to (3.1), and proves in Lemma 3.1 that M_l(t) = (X(t)+gamma/(2+delta))_(l)/(t+beta)_(l) is a martingale; the beta mixture is then identified from rising-factorial moments, with no fitted constant or externally imported limit. The m>1 descendant statement in Theorem 2.3 does not smuggle in its conclusion: the m=1 input is proved as Theorem 2.2 in the same paper, and the transfer is via Lemma 3.3, whose block-inclusion inequality is proved directly; the underlying delta-extension coupling is also proved in the Appendix rather than simply cited. Likewise, Theorem 2.4 for UAM uses the exact increment probability (3.15) and the elementary inclusion G_{t,1} subset of G_{t,m}. The greedy matching and independent set results are derived by writing conditional drifts from the attachment probabilities (e.g., (5.4)-(5.5), (6.2)-(6.4)) and then applying the self-contained Lemma 4.2/4.3; the limiting constants rho, r_m, w_m are deterministic roots of those drift functions, not fitted parameters. Self-citations appear (notably Pittel [35] for the delta=0 martingale), but the paper explicitly reproves that martingale for all delta in Lemma 3.1, and the Hofstad coupling is re-derived in the Appendix, so none of the citations is load-bearing for the central claim. No equation is equivalent to its input by construction, and no prediction is a renamed fit.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central results are theorem-level statements about random graph processes; no data are fitted and no numerical constants are tuned. The only inputs are model parameters such as m, delta, and the root r, plus standard probabilistic tools. The main nonstandard structural input is the delta-collapsing coupling, which is proved in the Appendix. The main incompleteness is in the loops-allowed PAM matching extension, which is presented as a proof sketch.

assumptions (5)
  • standard math Martingale convergence theorem, Borel-Cantelli lemma, and standard probability convergence tools.
    Used throughout Sections 3 and 4 to convert martingale moment information into almost sure limits and rates.
  • standard math Chernoff bound for sums of independent Bernoulli variables, cited to Janson, Luczak, and Rucinski.
    Core input to Lemma 4.2, which drives all greedy algorithm convergence rates.
  • standard math Rising factorial moment identities and signless Stirling number generating functions from Comtet.
    Used in Lemma 3.1 to prove the martingale property of the new factorial martingales.
  • domain assumption The delta-collapsing coupling between G_{m,delta}(t) and G_{1,delta/m}(mt) is valid.
    The proof in the Appendix verifies the coupling; the paper also uses it as the bridge from m=1 to m>1 in Theorem 2.3.
  • domain assumption The greedy matching algorithm's arbitrary choice among multiple newly available unmatched neighbors does not change the limiting counts.
    Used in Section 5; the proofs only use the count of unmatched vertices selected, so the tie rule should not matter, but this is not separately examined.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Giant descendant trees, matchings and independent sets in the age-biased attachment graphs." pith.science (2026). https://pith.science/paper/KEZSEQOQ

@misc{pith2026190802407,
  author       = {Pith},
  title        = {Pith review of: Giant descendant trees, matchings and independent sets in the age-biased attachment graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KEZSEQOQ}},
  note         = {Machine review of arXiv:1908.02407}
}
abstract

We study two models of an age-biased graph process: the $\delta$-version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with $m$ attachments for each of incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for $m=1$, to a limit whose distribution is a mixture of two beta-distributions and a single beta-distribution respectively, and that for $m>1$ the limit is $1$. We also analyze the likely performance of two greedy (online) algorithms, for a large matching set and a large independent set, and determine--for each model and each greedy algorithm--both a limiting fraction of vertices involved and an almost sure convergence rate.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 33 canonical work pages

  1. [1]

    Acan and B

    H. Acan and B. Pittel, On connectivity, conductance and bootstrap percolation fo r the uniformly random k-out, age-biased graph , Random Structures and Algorithms, (2019), 1–26

    work page 2019

  2. [2]

    Acan and P

    H. Acan and P. Hitczenko, On a memory game and preferential attachment graphs , Advances in Applied Probability 48 (2) (2016) 585–609

    work page 2016

  3. [3]

    Barab´ asi and R

    I. Barab´ asi and R. Albert,Emergence of scaling in random networks , Science 286 (1999) 509–512

    work page 1999

  4. [4]

    Berger, C

    N. Berger, C. Borgs, J. T. Chayes and A. Saberi, Asymptotic behavior and distributional limits of preferen tial attachment graphs, Annals of Probability 42 (1) (2014) 1–40

    work page 2014

  5. [5]

    Bollob´ as,Random Graphs, 2nd Edition (2001)

    B. Bollob´ as,Random Graphs, 2nd Edition (2001)

    work page 2001

  6. [6]

    Bollob´ as, O

    B. Bollob´ as, O. Riordan, J. Spencer and G. Tusn´ ady, The degree sequence of a scale-free random graph process, Random Structures and Algorithms 18 (2001) 279–290

    work page 2001

  7. [7]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan,The diameter of a scale-free random graph , Combinatorica 4 (1) (2004) 5–34

    2004

  8. [8]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan, Linearized chord diagrams and an upper bound for the Vassili ev invariants , J. Knot Theory Ramifications 9 (7) (2000) 847–853

    work page 2000

Show all 35 references
  1. [9]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan,Robustness and vulnerability of scale-free random graphs , Internet Mathematics 1 (2003) 1-35

    2003

  2. [10]

    Bollob´ as and O

    B. Bollob´ as and O. Riordan,Mathematical results on scale-free random graphs , Ch. 1 in Handbook of Graphs and Networks: from the Genome to the Internet (2002)

    2002

  3. [11]

    Bollob´ as, C

    B. Bollob´ as, C. Borgs, J. Chayes and O. Riordan,Directed scale-free graphs, Proceedings of the 14th Annual ACM-SIAM SODA Conference (2003) 132–139

    2003

  4. [12]

    Borgs, M

    C. Borgs, M. Brautbar, J. Chayes, S. Khanna and B. Lucier, The power of local information in social networks , International Workshop on Internet and Network Economics W INE 2012: Internet and Network Economics (2012) 406-419

    2012

  5. [13]

    Comtet, Advanced Combinatorics, Dordrecht-Holland (1974)

    L. Comtet, Advanced Combinatorics, Dordrecht-Holland (1974)

    1974

  6. [14]

    Cooper and A.M

    C. Cooper and A.M. Frieze, Crawling on web graphs , Internet Mathematics 1 (2003) 57-90

    2003

  7. [15]

    Cooper and A.M

    C. Cooper and A.M. Frieze, The cover time of the preferential attachment graph , Journal of Combinatorial Theory, Series B 97 (2007) 269-290

    2007

  8. [16]

    Cooper, R

    C. Cooper, R. Klasing and M. Zito, Lower bounds and algorithms for dominating sets in web graph s, Internet Mathematics 2 (2005), 275-300

    2005

  9. [17]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi, On random graphs I,Publ. Math. Debrecen 6 (1959) 290-297

    1959

  10. [18]

    Flaxman, A.M

    A. Flaxman, A.M. Frieze and T. Fenner, High degree vertices and eigenvalues in the preferential at tachment graph, Internet Mathematics 2 (2005) 1-20

    2005

  11. [19]

    Frieze, X

    A.M. Frieze, X. P´ erez-Gim´ enez, P. Pra/suppress lat and B. Reiniger, Perfect matchings and Hamiltonian cycles in the preferential attachment model , Random Structures and Algorithms 54 (2019) 258–288

    2019

  12. [20]

    Frieze and M

    A.M. Frieze and M. Karo´ nski,Introduction to Random Graphs , Cambridge University Press (2016)

    2016

  13. [21]

    Frieze and W

    A.M. Frieze and W. Pegden, Looking for vertex number one , Annals of Applied Probability 27 (2017) 582-630

    2017

  14. [22]

    Gilbert, Random graphs, Annals of Mathematical Statistics 30 (1959) 1141-1144

    E.N. Gilbert, Random graphs, Annals of Mathematical Statistics 30 (1959) 1141-1144

    1959

  15. [23]

    Mihail, C

    M. Mihail, C. Papadimitriou and A. Saberi, On certain connectivity properties of the internet topolog y, Journal of Computer and System Sciences 72 (2006), no.2, 239 –251

    2006

  16. [24]

    Janson, T

    S. Janson, T. /suppress Luczak and A. Ruci´ nski,Random Graphs, Wiley, New York, 2000

    2000

  17. [25]

    Janson, Random recursive trees and preferential attachment trees a re random split trees , Combinatorics, Probability and Computing 28 (2019) 81–99

    S. Janson, Random recursive trees and preferential attachment trees a re random split trees , Combinatorics, Probability and Computing 28 (2019) 81–99

    2019

  18. [26]

    Janson and L

    S. Janson and L. Warnke, Preferential attachment without vertex growth: emergence of the giant component , preprint. https://arxiv.org/pdf/1904.11861.pdf

    1904 arXiv

  19. [27]

    Katona and T

    Z. Katona and T. M´ ori,A new class of scale free random graphs , Statistics & Probability Letters, 76 (2006) 1587–1593

    2006

  20. [28]

    van der Hofstad, Random Graphs and Complex Networks, V1 , Cambridge University Press (2017)

    R. van der Hofstad, Random Graphs and Complex Networks, V1 , Cambridge University Press (2017). AGE-BIASED ATTACHMENT GRAPHS 25

    2017

  21. [29]

    M´ ori,On random trees , Studia Sci

    T. M´ ori,On random trees , Studia Sci. Math. Hungar. 39 (2003) 143–155

    2003

  22. [30]

    M´ ori,The maximum degree of the Barab´ asi–Albert random tree , Combin

    T. M´ ori,The maximum degree of the Barab´ asi–Albert random tree , Combin. Prob. Computing 14 (2005) 339–348

    2005

  23. [31]

    Pek¨ oz, A

    E. Pek¨ oz, A. R¨ ollin and N. Ross,Joint degree distributions of preferential attachment ran dom graphs , Ad- vances in Applied Probability 49 (2017) (2) 368–387

    2017

  24. [32]

    Pittel, On the probable behavior of some algorithms for finding the st ability number of a graph , Math

    B. Pittel, On the probable behavior of some algorithms for finding the st ability number of a graph , Math. Proc. Camb. Phil. Soc. 92 (1982) 511–26

    1982

  25. [33]

    Pittel, Note on the heights of random recursive trees and random m-ar y search trees, Random Structures Algorithms 5 (1994), 337–347

    B. Pittel, Note on the heights of random recursive trees and random m-ar y search trees, Random Structures Algorithms 5 (1994), 337–347

    1994

  26. [34]

    Pittel, On a random graph evolving by degrees , Adv

    B. Pittel, On a random graph evolving by degrees , Adv. in Math. 223 (2010) 619–671

    2010

  27. [35]

    Pittel, On Bollob´ as-Riordan random pairing model of preferential attachment graph, Random Structures Algorithms, forthcoming

    B. Pittel, On Bollob´ as-Riordan random pairing model of preferential attachment graph, Random Structures Algorithms, forthcoming. https:// arxiv.org/pdf/1811.10764.pdf Appendix In order to show that the coupling described in Section 3 really works, we can compute the probabil...

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.