Introductory Workshop: Probability and Statistics of Discrete Structures: Asymptotic enumeration of discrete structures: what, how and why
Presenter
January 30, 2025
Keywords:
- Network models and random graphs
- statistcal learning and network inference
- counting and sampling discrete structures
- dynamics on networks
- probabilistic analysis of network algorithms
MSC:
- 05C80 - Random graphs (graph-theoretic aspects)
- 60C05 - Combinatorial probability
Abstract
Asymptotic enumeration involves finding an approximate formula for the size of a combinatorial set, with a relative error that gets smaller as the size of the set grows. For example, we might be interested in the number of hypergraphs with a given number of vertices and satisfying some other nice properties, and how this number behaves as the number of vertices tends to infinity. I will describe some methods for obtaining asymptotic enumeration formulae and some applications to the analysis of random graphs and hypergraphs.