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

Michael Wallner

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

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.PRData Structures and Algorithmsmath-phmath.MPmath.NT

Catalog footprint

What is connected

11works
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

11 published item(s)

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
preprint2022arXiv

Enumeration of $d$-combining Tree-Child Networks

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for {\it bicombining tree-child networks} which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to {\it $d$-combining tree-child networks} where every reticulation node has now $d\geq 2$ parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks

We answer some questions on the asymptotics of ballot walks raised in [Personal Journal Shalosh B Ekhad and Doron Zeilberger, Apr 5, 2021; see also arXiv:2104.01731] and prove that these models are not D-finite. This short note demonstrates how the powerful tools developed in the last decades on lattice paths in convex cones help us to answer some challenging problems that were out of reach for a long time. On the way we generalize tandem walks to the family of large tandem walks whose steps are of arbitrary length and map them bijectively to a generalization of ballot walks in three dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The binary digits of n+t

The binary sum-of-digits function $s$ counts the number of ones in the binary expansion of a nonnegative integer. For any nonnegative integer $t$, T.~W.~Cusick defined the asymptotic density $c_t$ of integers $n\geq 0$ such that \[s(n+t)\geq s(n).\] In 2011, he conjectured that $c_t>1/2$ for all $t$ -- the binary sum of digits should, more often than not, weakly increase when a constant is added. In this paper, we prove that there exists an explicit constant $M_0$ such that indeed $c_t>1/2$ if the binary expansion of $t$ contains at least $M_0$ maximal blocks of contiguous ones, leaving open only the "initial cases" -- few maximal blocks of ones -- of this conjecture. Moreover, we sharpen a result by Emme and Hubert (2019), proving that the difference $s(n+t)-s(n)$ behaves according to a Gaussian distribution, up to an error tending to $0$ as the number of maximal blocks of ones in the binary expansion of $t$ grows.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A half-normal distribution scheme for generating functions

We present a general theorem on the structure of bivariate generating functions which gives sufficient conditions such that the limiting probability distribution is a half-normal distribution. If $X$ is a normally distributed random variable with zero mean, then $|X|$ obeys a half-normal distribution. In the second part, we apply our result to prove three natural appearances in the domain of lattice paths: the number of returns to zero, the height, and the sign changes are under zero drift distributed according to a half-normal distribution. This extends known results to a general step set. Finally, our result also gives a new proof of Banach's matchbox problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Compacted binary trees admit a stretched exponential

A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size $n$ grows asymptotically like $$Θ\left( n! \, 4^n e^{3a_1n^{1/3}} n^{3/4} \right),$$ where $a_1\approx-2.338$ is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large $n$ to determine the asymptotic form. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A half-normal distribution scheme for generating functions and the unexpected behavior of Motzkin paths

We present an extension of a theorem by Michael Drmota and Michèle Soria [Images and Preimages in Random Mappings, 1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associated bivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian, or a convolution of the last two distributions. We conclude with three natural appearances of such a limiting distribution in the domain of Motzkin paths.

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
preprint2016arXiv

Lattice paths of slope 2/5

We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5.This answers to Knuth's problem \\#4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014.Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths. A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack),promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic,and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkov{\v s}ek.We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Some reflections on directed lattice paths

This article analyzes directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y=0 thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet ("Analytic combinatorics of directed lattice paths"), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of Łukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier-Flajolet model (partly because new "critical compositions" appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a role in the "universal" behavior of such walks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The kernel method for lattice paths below a line of rational slope

We analyse some enumerative and asymptotic properties of lattice paths below a line of rational slope. We illustrate our approach with Dyck paths under a line of slope $2/5$. This answers Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014. Our approach extends the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths to the case of generating functions involving several dominant singularities, and has applications to a full class of problems involving some "periodicities". A key ingredient in the proof is the generalization of an old trick by Knuth himself (for enumerating permutations sortable by a stack), promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic, and they offer some new combinatorial identities, which can also be tackled in the A=B spirit of Wilf-Zeilberger-Petkovsek. We show how to obtain similar results for any rational slope. An interesting case is e.g. Dyck paths below the slope $2/3$ (this corresponds to the so-called Duchon's club model), for which we solve a conjecture related to the asymptotics of the area below such lattice paths. Our work also gives access to lattice paths below an irrational slope (e.g. Dyck paths below $y=x/\sqrt{2}$), a problem that we study in a companion article.

0 citations0 reviewsNo code linkedOpen access