Recent Advances in Counting Sparse Graphs
summary
Asks whether upper tails for subgraph counts follow a variational entropy formula and shows a sufficient condition: the gradient of the counting polynomial must admit a low-complexity gradient condition (its image has a small epsilon-net). Proves a rigorous mean-field approximation giving log-probabilities ≈ −φP(t) plus explicit smoothness/complexity errors, and applies it to triangles when P decays no faster than about N^(−1/42) (conjectured extendable to N^(−1/2)). Clique constructions give matching lower bounds and the dense case reduces to a solved variational problem.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:26The upper tail problem in random graphs
- 1:44Upper tails for triangles
- 5:12Large deviations for triangle counts
- 6:31Partial solution
- 8:33Generalization
- 11:20Large deviations for subgraph counts
- 14:51A general problem
- 15:59The naive mean field approximation
- 19:18Low complexity gradient condition
- 21:20ID Ising model
- 22:00Curie-Weiss model
- 23:06Subgraph counts in sparse random graphs
- 28:51Example 3 contd.
- 31:19Nonlinear large deviations: The main result
- 32:47Main result, contd.
- 34:08Statement of the main result
- 37:38Proof sketch contd.
- 42:50Summary
related talks
56mTesting Thresholds for High-dimensional Sparse Random Geometric Graphs
41mReducibility and Statistical-Computational Gaps from Secret Leakage
55mDistribution-Free Models of Social and Information Networks
01h 04mHigher-dimensional Expansion of Random Geometric Complexes
01h 04mNonparametric Bayesian Methods: Models, Algorithms, and Applications IV
01h 31mGraphons and Graph Limits 2
56mEntropy, Capacity, and Counting
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials