4 papers · 2 filters
Enumerating Lambda Terms by Weighted Length of Their De Bruijn Representation
Olivier Bodini, Bernhard Gittenberger, Zbigniew Gołębiewski
John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of 0-1-strings using the de Bruijn representation along with a weighting schem…
On the shape of random Pólya structures
Bernhard Gittenberger, Emma Yu Jin, Michael Wallner
Panagiotou and Stufler recently proved an important fact on their way to establish the scaling limits of random Pólya trees: a uniform random Pólya tree of size consists of a c…
Threshold functions for small subgraphs: an analytic approach
Gwendal Collet, Élie de Panafieu, Danièle Gardy +2
We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, including the case of constrained degrees. Our approach relies heavily on…
Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers +1
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 e…