The Thin Matching Problem
Anari, Charikar and Ramakrishnan asked whether every fractional perfect matching admits a perfect matching that is -thin with respect to it, meaning it crosses every cut at most times the fractional amount. Resolved up to polylogarithmic factors.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-assisted
- Method
- Argument
- Field
- Graph algorithms
- Posed by
- Nima Anari, Moses Charikar, Prasanna Ramakrishnan
- Year posed
- 2023
- Years open
- 3y
- Solved
- 2026-05-31
- Model
- GPT-5.5 Pro
- Vendor
- OpenAI
- Collaborators
- Alireza Haqi, Shayan Oveis Gharan
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
up to polylogarithmic factors
What the AI did
The acknowledgement says the authors used GPT-5.5 Pro during the research, and points at the connection to cut-tree sparsification as where it mattered.
Verification
arXiv preprint; not yet peer-reviewed.
Source
arXiv:2606.01330 - On Thin Perfect Matchings up to Polylogarithmic Factors