Skip to Main content Skip to Navigation
New interface
Journal articles

And/or trees: a local limit point of view

Abstract : We present here a new and universal approach for the study of random and/or trees, unifying in one framework many different models, including some novel models, not yet understood in the literature. An and/or tree is a Boolean expression represented in (one of) its tree shape. Fix an integer $k$, take a sequence of random (rooted) trees of increasing sizes, say $(t_n)_{n\ge 1}$, and label each of these random trees uniformly at random in order to get a random Boolean expression on $k$ variables.
We prove that, under rather weak local conditions on the sequence of random trees $(t_n)_{n\ge 1}$, the distribution induced on Boolean functions by this procedure converges as $n\to\infty$. In particular, we characterise two different behaviours of this limit distribution depending on the shape of the local limit of $(t_n)_{n\ge 1}$: a degenerate case when the local limit has no leaves; and a non degenerate case, which we are able to describe in more details under stronger but reasonable conditions. In this latter case, we provide a relationship between the probability of a given Boolean function and its complexity. The examples we cover include, in a unified way, trees that interpolate between models with logarithmic typical distances (such as random binary search trees) and other ones with square root typical distances (such as conditioned Galton--Watson trees).
Document type :
Journal articles
Complete list of metadata
Contributor : Nicolas Broutin Connect in order to contact the contributor
Submitted on : Tuesday, October 27, 2015 - 12:13:04 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:05 PM

Links full text


  • HAL Id : hal-01220794, version 1
  • ARXIV : 1510.06691



Nicolas Broutin, Cécile Mailler. And/or trees: a local limit point of view. Random Structures and Algorithms, In press. ⟨hal-01220794⟩



Record views