# Random expansions of trees with bounded height

arXiv: https://arxiv.org/abs/2410.11775 · HTML: https://mlsanity.com/paper/2410.11775/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2024.

## Built on by (most cited first, 3 of 3)

- [Domain size asymptotics for Markov logic networks](https://mlsanity.com/paper/2509.04192/) (2025)
- [A convergence law for continuous logic and continuous structures with finite domains](https://mlsanity.com/paper/2504.08923/) (2025)
- [A concentration result for multilayer feedforward neural networks](https://mlsanity.com/paper/2608.15335/) (2026)

## Abstract (arXiv)

We consider a sequence T = (Tn : n ∈ mathbbN^+) of trees Tn where, for some Delta ∈ mathbbN^+ every Tn has height at most Delta and as n → ∞ the minimal number of children of a nonleaf tends to infinity. We can view every tree as a (first-order) τ-structure where τ is a signature with one binary relation symbol. For a fixed (arbitrary) finite and relational signature σ supseteq τ we consider the set Wn of expansions of Tn to σ and a probability distribution mathbbPn on Wn which is determined by a (parametrized/lifted) Probabilistic Graphical Model (PGM) mathbbG which can use the information given by Tn. The kind of PGM that we consider uses formulas of a many-valued logic that we call PLA^* with truth values in the unit interval [0, 1]. We also use PLA^* to express queries, or events, on Wn. With this setup we prove that, under some assumptions on T, mathbbG, and a (possibly quite complex) formula varphi(x1, ldots, xk) of PLA^*, as n → ∞, if a1, ldots, ak are vertices of the tree Tn then the value of varphi(a1, ldots, ak) will, with high probability, be almost the same as the value of psi(a1, ldots, ak), where psi(x1, ldots, xk) is a ``simple'' formula the value of which can always be computed quickly (without reference to n), and psi itself can be found by using only the information that defines T, mathbbG and varphi. A corollary of this, subject to the same conditions, is a probabilistic convergence law for PLA^*-formulas.