Counting Degree-constrained Subgraphs and Orientations
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Discusses algorithms for counting subgraphs and orientations of a graph subject to degree constraints, focusing on deterministic methods. Covers combinatorial and algorithmic techniques—likely including graph limits, matchings, and partition-function-related tools—to obtain exact or approximate counts under degree restrictions.
AI-written summary · about
chapters (15)
- 0:00Start
- 6:04Matching polynomial
- 7:38Truncated 3-regular graphs
- 9:32Origins: matchings
- 11:42Normal factor graphs
- 15:45Counting degree constrained subgraphs
- 22:30Ring of constants
- 23:56Eigenvectors
- 27:35Orientation polynomial
- 31:27Orientations of 3-regular graphs
- 34:23Upper bound
- 35:12Bethe approximation
- 36:35Two sufficient conditions
- 37:22Small degree cases
- 38:10Matchings of truncated graphs