Truly linear sparsifier conjecture for set systems
Let be a set system, let be weights, and let . Write for the chain length of . A sparsifier retains a selected subset of coordinates while approximating the relevant set-system quantities within multiplicative error . Truly linear sparsifier conjecture. There exists a sparsifier of retaining only
many coordinates. This conjecture seeks an analogue for arbitrary set systems of the edge bounds for graph cut sparsification; the paper's results give sparsifiers whose size depends on accuracy and chain length, but do not establish this bound in general.
References
Primary source
Joshua Brakensiek, Venkatesan Guruswami and Aaron Putterman, “Multiplicative error set system sparsification: A simpler proof via chain length contraction”, arXiv:2605.01508 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.