The Foata-Fuchs proof of Cayley's formula, and its probabilistic uses

2021/07/20 by Louigi Addario‐Berry, Serte Donderwinkel, Addario-Berry, Louigi +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #05C05 #60C05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.2107.09726

openalex publication_date 2021/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a very simple bijective proof of Cayley's formula due to Foata and Fuchs (1970). This bijection turns out to be very useful when seen through a probabilistic lens; we explain some of the ways in which it can be used to derive probabilistic identities, bounds, and growth procedures for random trees with given degrees, including random d-ary trees. We also introduce a partial order on the degree sequences of rooted trees, and conjecture that it induces a stochastic partial order on heights of random rooted trees with given degrees.

Cited by

• Universal diameter bounds for random graphs with given degrees

Related

• An Elementary Proof of the Cayley Formula Using Random Maps
• A Simple Proof of the Cayley Formula using Random Graphs
• Random trees have height O(√(n))
• Random planar trees and the Jacobian conjecture
• Random Trees and General Branching Processes