Thin perfect matchings relative to fractional matchings
Follow the latest progress by email.
Relative to a fractional perfect matching, how thin can an integral perfect matching be across every cut? In the relaxed problem its edges may lie outside the fractional matching’s support; the support-constrained variant is different.
Why it matters and what counts as progress
Why it matters: Thin matchings would control cut loads in metric-distortion applications.
What counts as progress: A better relaxed thinness factor toward O(1), or a sharper obstruction; polylogarithmic relaxed bounds do not remove the Ω(n) support-restricted barrier.
How the problem developed
- 9 Jul 2023 · Conjecture [1]
Nima Anari, Moses Charikar and Prasanna Ramakrishnan Introduced thin perfect matchings in the metric-distortion setting and conjectured a constant-thin matching relative to any fractional perfect matching.
- 31 May 2026 · Partial result [2]
Alireza Haqi and Shayan Oveis Gharan Proved a polylogarithmic thinness bound when edges outside the fractional matching's support are allowed, and showed support-constrained thinness can require linear dependence on the vertex count.
AI contribution
On Thin Perfect Matchings up to Polylogarithmic Factors
A connection from relaxed thin perfect matching to a single-tree cut sparsifier helps yield an O(log n log log n)-thin perfect matching relative to any fractional perfect matching, allowing edges outside its support. The separate O(n log n) bound requires support-constrained edges.
Sources
Website timeline
Publication dates and editorial changes.