Truly linear sparsifier conjecture for set systems

Less than 1 year old · traced to

Let S⊆2[m]\mathcal S \subseteq 2^{[m]} be a set system, let w:[m]→R≥0w:[m]\rightarrow\mathbb{R}_{\geq 0} be weights, and let ϵ>0\epsilon>0. Write CL⁡(S)\operatorname{CL}(\mathcal S) for the chain length of S\mathcal S. A (1±ϵ)(1\pm\epsilon) sparsifier retains a selected subset of coordinates while approximating the relevant set-system quantities within multiplicative error 1±ϵ1\pm\epsilon. Truly linear sparsifier conjecture. There exists a (1±ϵ)(1\pm\epsilon) sparsifier of S\mathcal S retaining only

O(CL⁡(S)ϵ2)O\left(\frac{\operatorname{CL}(\mathcal S)}{\epsilon^2}\right)

many coordinates. This conjecture seeks an analogue for arbitrary set systems of the O(n/ϵ2)O(n/\epsilon^2) 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

Never refreshed

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.