Introductory Workshop: Probability and Statistics of Discrete Structures: Large deviations for triangles in random graphs in the critical regime
Presenter
January 31, 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
A classic problem in probability theory and combinatorics is to estimate the probability that the random graph G(n,p) contains no triangles. This problem can be viewed as a question in "non-linear large deviations". The asymptotics of the logarithm of this probability (and related lower tail probabilities) are known in two distinct regimes. When p>> 1/\sqrt{n}, at this level of accuracy the probability matches that of G(n,p) being bipartite; and when p