BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Alois Panholzer contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
This short note serves an addendum to the article "Destruction of very simple trees" by Fill, Kapur and Panholzer (2004). Therein, the limit law of one-sided tree destruction with a toll function was determined by its moment sequence. We add an identification of the limit law, using recent results of Bertoin (2022), in terms of the local time of a noise reinforced Bessel process.
We consider the process of uncovering the vertices of a random labeled tree according to their labels. First, a labeled tree with $n$ vertices is generated uniformly at random. Thereafter, the vertices are uncovered one by one, in order of their labels. With each new vertex, all edges to previously uncovered vertices are uncovered as well. In this way, one obtains a growing sequence of forests. Three particular aspects of this process are studied in this work: first the number of edges, which we prove to converge to a stochastic process akin to a Brownian bridge after appropriate rescaling. Second, the connected component of a fixed vertex, for which different phases are identified and limiting distributions determined in each phase. Lastly, the largest connected component, for which we also observe a phase transition.
In this work we analyze bucket increasing tree families. We introduce two simple stochastic growth processes, generating random bucket increasing trees of size $n$, complementing the earlier result of Mahmoud and Smythe for bucket recursive trees. On the combinatorial side, we define multilabelled generalizations of the tree families $d$-ary increasing trees and generalized plane-oriented recursive trees. Additionally, we introduce a clustering process for ordinary increasing trees and relate it to bucket increasing trees. We discuss in detail the bucket size two and present a bijection between such bucket increasing tree families and certain families of graphs called increasing diamonds, providing an explanation for phenomena observed by Bodini et al.
We study the enumeration problem for different kind of tree parking functions introduced recently, called tree parking functions, tree parking distributions, prime tree parking functions, and prime tree parking distributions, for rooted labelled trees of important combinatorial tree families including labelled ordered, unordered and binary trees. Using combinatorial decompositions of the underlying structures yields, after solving the resulting equations, implicit characterizations of suitable generating functions of the total number of such tree parking functions for trees of size $n$ and $n$ successful drivers, from which we obtain exact and asymptotic enumeration results. The approach can be extended to the general situation of tree parking functions for trees of size $n$ and $m<n$ drivers for which we are also able to characterize the generating functions solutions, which allow, by applying analytic combinatorics techniques, a study of the asymptotic behaviour of the total number of tree parking functions and distributions for $n \to \infty$ depending on the load factor $0 < α= \frac{m}{n} < 1$.
We generalize the concept of ascending and descending runs from permutations to rooted labelled trees and mappings, i.e., functions from the set $\{1, \dots, n\}$ into itself. A combinatorial decomposition of the corresponding functional digraph together with a generating functions approach allows us to perform a joint study of ascending and descending runs in labelled trees and mappings, respectively. From the given characterization of the respective generating functions we can deduce bivariate central limit theorems for these quantities. Furthermore, for ascending runs (or descending runs) we gain explicit enumeration formulae showing a connection to Stirling numbers of the second kind. We also give a bijective proof establishing this relation, and further state a bijection between mappings and labelled trees connecting the quantities in both structures.
We introduce the problem of isolating several nodes in random recursive trees by successively removing random edges, and study the number of random cuts that are necessary for the isolation. In particular, we analyze the number of random cuts required to isolate $\ell$ selected nodes in a size-n random recursive tree for three different selection rules, namely (i) isolating all of the nodes labelled 1,2,...,$\ell$ (thus nodes located close to the root of the tree), (ii) isolating all of the nodes labelled n+1-$\ell$,n+2-$\ell$,...,n (thus nodes located at the fringe of the tree), and (iii) isolating $\ell$ nodes in the tree, which are selected at random before starting the edge-removal procedure. Using a generating functions approach we determine for these selection rules the limiting distribution behavior of the number of cuts to isolate all selected nodes, for $\ell$ fixed and n tending to infinity.
We consider so-called simple families of labelled trees, which contain, e.g., ordered, unordered, binary and cyclic labelled trees as special instances, and study the global and local behaviour of the number of inversions. In particular we obtain limiting distribution results for the total number of inversions as well as the number of inversions induced by the node labelled j in a random tree of size n.
We use death processes and embeddings into continuous time in order to analyze several urn models with a diminishing content. In particular we discuss generalizations of the pill's problem, originally introduced by Knuth and McCarthy, and generalizations of the well known sampling without replacement urn models, and OK Corral urn models.
We introduce a random graph model based on k-trees, which can be generated by applying a probabilistic preferential attachment rule, but which also has a simple combinatorial description. We carry out a precise distributional analysis of important parameters for the network model such as the degree, the local clustering coefficient and the number of descendants of the nodes and root-to-node distances. We do not only obtain results for random nodes, but in particular we also get a precise description of the behaviour of parameters for the j-th inserted node in a random k-tree of size n, where j = j(n) might grow with n. The approach presented is not restricted to this specific k-tree model, but can also be applied to other evolving k-tree models.