The Six- and the Eight-vertex Models and Counting Perfect Matchings
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Gives an FPRAS claim: a directed-loop Markov chain rapidly mixes when Z2/Z0 is polynomially bounded, yielding an FPS in disordered region for many six- and eight-vertex parameters; proves closure of 4-ary gadget constraints under reconstruction and uses circuit-pairing decompositions to show nonnegative induced weights; shows hardness via AP-reductions from Max‑IS and Max‑Cut and pins a subregion equivalent to approximately counting perfect matchings by implementing constraint functions with weighted matchgates.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:24Sixvertex Model
- 1:50Square Ice
- 4:03Generalized Models
- 7:44Phase Transition
- 12:39Directed Loop Algorithm
- 14:05Technical Lemma
- 15:25For Reconstruction
- 16:25Structural Lemma
- 16:59Decomposition
- 19:19Closure Property
- 21:09Eightvertex Model
- 28:55Computational Complexity
- 30:26Proof
- 31:24Constraint Functions
- 32:24Geometric Proof
- 36:35Open Problems
- 37:19Regular Graphs