Truly linear sparsifier conjecture for set systems

Let S2[m]\mathcal S \subseteq 2^{[m]} be a set system, let w:[m]R0w:[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.

Sources & referencesView supporting material

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.