Formulas and asymptotics of hypergraph Catalan numbers

2025/08/12 by Hainzl, Eva-Maria
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2508.08865

Abstract

Tree walks are a class of closed walks on a complete graph constrained to span trees. In this work, we focus on a special subclass called k-tours, which were recently introduced by Gunnells and are enumerated by the hypergraph Catalan numbers c_n^(k). Gunnells conjectured an asymptotic formula for c_n^(k) which we confirm through an alternative approach to their enumeration. As it turns out, the asymptotic growth is governed by the number of k-tours on star-like trees.

Citations

• Tree walks and the spectrum of random graphs
• Hypergraph matrix models and generating functions
• Generalized Catalan numbers from hypergraphs
• Spectral atoms of unimodular random trees
• Every totally real algebraic integer is a tree eigenvalue

Related

• Counting closed walks in infinite regular trees using Catalan and Borel's triangles
• Generalized Catalan numbers from hypergraphs
• Enumerating runs, valleys, and peaks in Catalan words
• Hypergraph Fuss-Catalan Numbers
• Action graphs and Catalan numbers