BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Bernhard Gittenberger

Bernhard Gittenberger appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRDiscrete Mathematicsmath.LOData Structures and AlgorithmsLogic in Computer SciencePopulations and Evolution

Catalog footprint

What is connected

12works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

12 published item(s)

preprint2026arXiv

Combinatorial comparison of general galled trees, time-consistent galled trees, and simplex time-consistent galled trees

Rooted binary phylogenetic networks are extensions of rooted binary trees, adding reticulation nodes that are designed to represent evolutionary processes that involve hybridization events. Enumerative combinatorics studies have counted leaf-labeled phylogenetic networks in a variety of classes, finding that when the number of reticulations is fixed, the time-consistent galled trees are asymptotically less numerous than each of several network classes that had been previously examined. Here we provide enumerative results on two additional network classes: general galled trees and simplex time-consistent galled trees. We show that for a fixed number of galls, as the number of leaves goes to infinity, the asymptotic count of general galled trees is identical to that of time-consistent galled trees, whereas the count of simplex time-consistent galled trees is smaller. If the number of galls is not restricted, then the asymptotic approximations all differ: simplex time-consistent galled trees are less numerous than time-consistent galled trees, which are in turn less numerous than general galled trees. We also report a variety of additional results: recursions to count the studied networks with small numbers of leaves a fixed number of galls, as well as enumerative results for unlabeled networks in the classes that we investigate.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height

A compacted binary tree is a graph created from a binary tree such that repeatedly occurring subtrees in the original tree are represented by pointers to existing ones, and hence every subtree is unique. Such representations form a special class of directed acyclic graphs. We are interested in the asymptotic number of compacted trees of given size, where the size of a compacted tree is given by the number of its internal nodes. Due to its superexponential growth this problem poses many difficulties. Therefore we restrict our investigations to compacted trees of bounded right height, which is the maximal number of edges going to the right on any path from the root to a leaf. We solve the asymptotic counting problem for this class as well as a closely related, further simplified class. For this purpose, we develop a calculus on exponential generating functions for compacted trees of bounded right height and for relaxed trees of bounded right height, which differ from compacted trees by dropping the above described uniqueness condition. This enables us to derive a recursively defined sequence of differential equations for the exponential generating functions. The coefficients can then be determined by performing a singularity analysis of the solutions of these differential equations. Our main results are the computation of the asymptotic numbers of relaxed as well as compacted trees of bounded right height and given size, when the size tends to infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Counting Phylogenetic Networks with Few Reticulation Vertices: Exact Enumeration and Corrections

In previous work, we gave asymptotic counting results for the number of tree-child and normal networks with $k$ reticulation vertices and explicit exponential generating functions of the counting sequences for $k=1,2,3$. The purpose of this note is two-fold. First, we make some corrections to our previous approach which overcounted the above numbers and thus gives erroneous exponential generating functions (however, the overcounting does not effect our asymptotic counting results). Secondly, we use our (corrected) exponential generating functions to derive explicit formulas for the number of tree-child and normal networks with $k=1,2,3$ reticulation vertices. This re-derives recent results of Carona and Zhang, answers their question for normal networks with $k=2$, and adds new formulas in the case $k=3$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A note on the scaling limits of random Pólya trees

Panagiotou and Stufler (arXiv:1502.07180v2) recently proved one important fact on their way to establish the scaling limits of random Pólya trees: a uniform random Pólya tree of size $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements on the bound of $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=Θ(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Finally, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

2-Xor revisited: satisfiability and probabilities of functions

The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses $x \oplus y$, is satisfiable. We revisit this classical problem by giving an alternative, explicit expression of this probability. We then consider a refinement of it, namely the probability that a random expression computes a specific Boolean function. The answers to both problems involve a description of 2-Xor expressions as multigraphs and use classical methods of analytic combinatorics by expressing probabilities through coefficients of generating functions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the number of lambda terms with prescribed size of their De Bruijn representation

John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of binary words. Later, Grygiel and Lescanne conjectured that the number of binary lambda terms with $m$ free indices and of size $n$ (encoded as binary words of length $n$) is $o(n^{-3/2} τ^{-n})$ for $τ\approx 1.963448\ldots$. We generalize the proposed notion of size and show that for several classes of lambda terms, including binary lambda terms with $m$ free indices, the number of terms of size $n$ is $Θ(n^{-3/2} ρ^{-n})$ with some class dependent constant $ρ$, which in particular disproves the above mentioned conjecture. A way to obtain lower and upper bounds for the constant near the leading term is presented and numerical results for a few previously introduced classes of lambda terms are given.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the number of unary-binary tree-like structures with restrictions on the unary height

We consider various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions concerning the unary nodes or abstractions, respectively: We either bound their number or the allowed levels of nesting. The enumeration is done by means of a generating function approach and singularity analysis. The generating functions are composed of nested square roots and exhibit unexpected phenomena in some of the cases. Furthermore, we present some observations obtained from generating such terms randomly and explain why usually powerful tools for random generation, such as Boltzmann samplers, face serious difficulties in generating lambda-terms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The relation between tree size complexity and probability for Boolean functions generated by uniform random trees

We consider a probability distribution on the set of Boolean functions in n variables which is induced by random Boolean expressions. Such an expression is a random rooted plane tree where the internal vertices are labelled with connectives And and OR and the leaves are labelled with variables or negated variables. We study limiting distribution when the tree size tends to infinity and derive a relation between the tree size complexity and the probability of a function. This is done by first expressing trees representing a particular function as expansions of minimal trees representing this function and then computing the probabilities by means of combinatorial counting arguments relying on generating functions and singularity analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Associative and commutative tree representations for Boolean functions

Since the 90's, several authors have studied a probability distribution on the set of Boolean functions on $n$ variables induced by some probability distributions on formulas built upon the connectors $And$ and $Or$ and the literals $\{x_{1}, \bar{x}_{1}, \dots, x_{n}, \bar{x}_{n}\}$. These formulas rely on plane binary labelled trees, known as Catalan trees. We extend all the results, in particular the relation between the probability and the complexity of a Boolean function, to other models of formulas: non-binary or non-plane labelled trees (i.e. Polya trees). This includes the natural tree class where associativity and commutativity of the connectors $And$ and $Or$ are realised.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Enumeration of generalized $BCI$ lambda-terms

We investigate the asymptotic number of elements of size $n$ in a particular class of closed lambda-terms (so-called $BCI(p)$-terms) which are related to axiom systems of combinatory logic. By deriving a differential equation for the generating function of the counting sequence we obtain a recurrence relation which can be solved asymptotically. We derive differential equations for the generating functions of the counting sequences of other more general classes of terms as well: the class of $BCK(p)$-terms and that of closed lambda-terms. Using elementary arguments we obtain upper and lowerestimates for the number of closed lambda-terms of size $n$. Moreover, a recurrence relation is derived which allows an efficient computation of the counting sequence. $BCK(p)$-terms are discussed briefly.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The degree profile of Pólya trees

We investigate the profile of random Pólya trees of size $n$ when only nodes of degree $d$ are counted in each level. It is shown that, as in the case where all nodes contribute to the profile, the suitably normalized profile process converges weakly to a Brownian excursion local time. Moreover, we investigate the joint distribution of the number of nodes of degree $d_1$ and $d_2$ in the levels of the tree.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Shape of Unlabeled Rooted Random Trees

We consider the number of nodes in the levels of unlabelled rooted random trees and show that the stochastic process given by the properly scaled level sizes weakly converges to the local time of a standard Brownian excursion. Furthermore we compute the average and the distribution of the height of such trees. These results extend existing results for conditioned Galton-Watson trees and forests to the case of unlabelled rooted trees and show that they behave in this respect essentially like a conditioned Galton-Watson process.

0 citations0 reviewsNo code linkedOpen access