{"id":"arxiv/2605.01508","url":"https://arxiv.org/abs/2605.01508","tags":["math.CO"],"score":0,"title":"Multiplicative error set system sparsification: A simpler proof via chain length contraction","domain":"math.CO","source":"arxiv","authors":["Joshua Brakensiek","Venkatesan Guruswami","Aaron Putterman"],"reviews":0,"subject":"math.CO","summary":"The chain length of a set family $\\mathcal{S} \\subseteq 2^{[m]}$ is the largest ascending sequence of sets in containment order in the union-closure of $\\mathcal S$. In this work, we provide a significantly simpler and more optimal characterization of the sparsifiability of set systems in terms of their chain length, improving on the work of Brakensiek and Guruswami [STOC 2025]. Our proof relies on a generalization of Karger's [SODA 1993] famous contraction algorithm and its recent linear algebraic extensions [Khanna-Putterman-Sudan SODA 2024], and our resulting bounds show that, just as VC…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-02","reactions":{}}