Counting Matchings via the Capacity Method
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Gives an explicit analytic route to lower-bound matchings: proves Gurvits-style capacity inequalities that reproduce Schrijver’s lower bound for perfect matchings in d-regular bipartite graphs and extends to k-matchings in biregular cases with an entropy-like factor and explicit constants. Uses the capacity of real-stable polynomials, computes marginals from d-stochasticity, and tracks how stability-preserving differential operators multiplicatively shrink capacity; constants are explicit (often tight) and the method produces computable lower bounds rather than just qualitative log‑concavity.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:57Outline
- 3:32Matchings Partition Function
- 4:44Univariate Matching Polynomial Plugin w-1 and consider the univariate polynomiat
- 6:41Beyond Newton's Inequalities
- 9:46Gurvits' Approach: Bipartite Perfect Matchings
- 20:02Polynomial Capacity
- 23:08From Capacity to Perfect Matchings
- 35:17Generalizing the Method
- 38:57Imperfect Matchings, Biregular Bipartite Graphs
- 40:28Csikvári's Approach: Bipartite Imperfect Matchings
- 43:22Applying the Capacity Method Question: Can we emulate what Gurvits did for perfect matchings?
- 45:38Applying the Capacity Method Recall the general plan
- 46:07A Few Interesting Details of the Proof