Multiplicative error set system sparsification: A simpler proof via chain length contraction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913083670134784 |
|---|---|
| author | Brakensiek, Joshua Guruswami, Venkatesan Putterman, Aaron |
| author_facet | Brakensiek, Joshua Guruswami, Venkatesan Putterman, Aaron |
| contents | 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 dimension characterizes the \emph{additive sparsifiability} of a set system, chain length governs the \emph{multiplicative sparsifiability}. As a corollary, we obtain improved bounds for weighted CSP sparsification. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_01508 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Multiplicative error set system sparsification: A simpler proof via chain length contraction Brakensiek, Joshua Guruswami, Venkatesan Putterman, Aaron Combinatorics 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 dimension characterizes the \emph{additive sparsifiability} of a set system, chain length governs the \emph{multiplicative sparsifiability}. As a corollary, we obtain improved bounds for weighted CSP sparsification. |
| title | Multiplicative error set system sparsification: A simpler proof via chain length contraction |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.01508 |