BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Cecilia Holmgren

Cecilia Holmgren contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.COmath.PRNetworking and Internet Architecture

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

6 published item(s)

preprint2020arXiv

A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees

We identify the mean growth of the independence number of random binary search trees and random recursive trees and show normal fluctuations around their means. Similarly we also show normal limit laws for the domination number and variations of it for these two cases of random tree models. Our results are an application of a recent general theorem of Holmgren and Janson on fringe trees in these two random tree models.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Cutting resilient networks -- complete binary trees

In our previous work, we introduced the random $k$-cut number for rooted graphs. In this paper, we show that the distribution of the $k$-cut number in complete binary trees of size $n$, after rescaling, is asymptotically a periodic function of $\lg n - \lg \lg n$. Thus there are different limit distributions for different subsequences, where these limits are similar to weakly 1-stable distributions. This generalizes the result for the case $k = 1$, i.e., the traditional cutting model, by Janson.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

K-cut on paths and some trees

We define the (random) $k$-cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except now a node must be cut $k$ times before it is destroyed. The first order terms of the expectation and variance of $\mathcal{X}_{n}$, the $k$-cut number of a path of length $n$, are proved. We also show that $\mathcal{X}_{n}$, after rescaling, converges in distribution to a limit $\mathcal{B}_{k}$, which has a complicated representation. The paper then briefly discusses the $k$-cut number of some trees and general graphs. We conclude by some analytic results which may be of interest.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Inversions in split trees and conditional Galton--Watson trees

We study $I(T)$, the number of inversions in a tree $T$ with its vertices labeled uniformly at random, which is a generalization of inversions in permutations. We first show that the cumulants of $I(T)$ have explicit formulas involving the $k$-total common ancestors of $T$ (an extension of the total path length). Then we consider $X_n$, the normalized version of $I(T_n)$, for a sequence of trees $T_n$. For fixed $T_{n}$'s, we prove a sufficient condition for $X_n$ to converge in distribution. As an application, we identify the limit of $X_n$ for complete $b$-ary trees. For $T_n$ being split trees, we show that $X_n$ converges to the unique solution of a distributional equation. Finally, when $T_n$'s are conditional Galton--Watson trees, we show that $X_n$ converges to a random variable defined in terms of Brownian excursions. By exploiting the connection between inversions and the total path length, we are able to give results that are stronger and much broader compared to previous work by Panholzer and Seitz.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Weakly 1-Stable Limiting Distribution for the Number of Random Records and Cuttings in Split Trees

We study the number of random records in an arbitrary split tree (or equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree, which is one specific case of split trees. Other important examples of split trees include $m$-ary search trees, quadtrees, medians of $(2k+1)$-trees, simplex trees, tries and digital search trees.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Novel Characteristics of Split Trees by use of Renewal Theory

We investigate characteristics of random split trees introduced by Devroye; split trees include for example binary search trees, $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees. More precisely: We introduce the use of renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality $n$ is constructed by distributing $n$ "balls" (which often represent "key numbers") in a subset of vertices of an infinite tree. One of our main results is to give a relation between the deterministic number of balls $n$ and the random number of vertices $N$. Devroye has found a central limit law for the depth of the last inserted ball so that most vertices are close to $\frac{\ln n}μ+\mathcal{O}\Big(\sqrt{\ln n}\Big)$, where $μ$ is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of vertices with depths $\geq\frac{\ln n}μ+\ln^{0.5+ε} n$ or depths $\leq\frac{\ln n}μ+\ln^{0.5+ε} n$ for any choice of $ε>0$. We also find the first asymptotic of the variances of the depths of the balls in the tree.

0 citations0 reviewsNo code linkedOpen access