What was already known
Anari, Charikar and Ramakrishnan conjectured O(1)-thin matchings. The paper shows support restriction can force Ω(n) thinness; the single-tree cut-sparsifier theorem used here already existed.
AI involvement
The authors credit GPT-5.5 Pro with the cut-tree-sparsifier connection. Alireza Haqi and Shayan Oveis Gharan wrote the proofs; Moses Charikar posed the problem and application, and Sricharan Arunapuram Rangaramanujam identified the prior theorem.
The specific model-found connection is central to the relaxed matching theorem, while the result combines human proofs and an existing sparsifier theorem.
Importance
Gives a polylogarithmic bound toward the thin-matching conjecture in the relaxed setting.
Limitations
Constant thinness remains open. The model is credited with the sparsifier connection, while Haqi and Oveis Gharan wrote the tree-pairing proof and Rangaramanujam pointed them to the prior sparsifier theorem. No completed check of the final proof is documented.
Technical verification
The paper supplies human-written proofs but does not explicitly document a completed check of the final theorem by a named checker or a machine check.
Human understanding
The authors’ proof overview and human-written Section 4 explain how tree-cut sparsification and bottom-up pairing control every cut.
Correction and publication history
First report of the relaxed thin-matching bound.
Read this published revision