Partial orders and monotonicity of logarithmic depth and height in preferential attachment trees
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914586585726976 |
|---|---|
| author | Mönch, Christian |
| author_facet | Mönch, Christian |
| contents | We study preferential attachment (PA) trees with general attachment functions. PA suggests an intuitive monotonicity: if high-degree vertices are rewarded more strongly, then the resulting tree should become shallower. We examine this principle through the constants governing two natural logarithmically growing observables, the insertion depth of the newest vertex and the height of the whole tree. Growth-ratio dominance (GRD) is the natural order on attachment functions, but we provide an explicit counterexample showing that GRD is not sufficient for either depth or height monotonicity at the level of logarithmic constants. The missing input is a dual tail-order condition on certain measures associated with the CMJ/BRW embedding of the PA tree. Under these profile-order assumptions we prove the expected monotonicity results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14741 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Partial orders and monotonicity of logarithmic depth and height in preferential attachment trees Mönch, Christian Probability 60J80 (primary), 05C80 (secondary) We study preferential attachment (PA) trees with general attachment functions. PA suggests an intuitive monotonicity: if high-degree vertices are rewarded more strongly, then the resulting tree should become shallower. We examine this principle through the constants governing two natural logarithmically growing observables, the insertion depth of the newest vertex and the height of the whole tree. Growth-ratio dominance (GRD) is the natural order on attachment functions, but we provide an explicit counterexample showing that GRD is not sufficient for either depth or height monotonicity at the level of logarithmic constants. The missing input is a dual tail-order condition on certain measures associated with the CMJ/BRW embedding of the PA tree. Under these profile-order assumptions we prove the expected monotonicity results. |
| title | Partial orders and monotonicity of logarithmic depth and height in preferential attachment trees |
| topic | Probability 60J80 (primary), 05C80 (secondary) |
| url | https://arxiv.org/abs/2602.14741 |