Multiplicative error set system sparsification: A simpler proof via chain length contraction

arxiv: 2605.01508 · v1 · submitted 2026-05-02 · 🧮 math.CO

Multiplicative error set system sparsification: A simpler proof via chain length contraction

Joshua Brakensiek , Venkatesan Guruswami , Aaron Putterman This is my paper

Pith reviewed 2026-05-09 14:10 UTC · model grok-4.3

classification 🧮 math.CO

keywords set system sparsificationchain lengthmultiplicative errorKarger's contractionunion-closureVC dimensionCSP sparsification

0 comments p. Extension

The pith

Chain length of a set system determines the size of its multiplicative-error sparsifier, just as VC-dimension does for additive error.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the longest ascending chain of sets under inclusion, taken inside the union-closure of the family, controls how small a sparsifier can be while preserving the approximate weight of every set up to a (1±ε) multiplicative factor. A simpler proof is obtained by extending Karger's contraction procedure so that contraction steps respect this chain-length bound and keep the failure probability under control. A sympathetic reader cares because the result supplies an explicit combinatorial parameter that replaces earlier, less intuitive conditions and immediately improves the size of sparsifiers for weighted constraint-satisfaction problems.

Core claim

Any set family whose union-closure has chain length at most k admits a sparsifier of size polynomial in k and 1/ε that (1±ε)-approximates the weight of every set; the proof proceeds by iteratively contracting elements while maintaining probabilities that accumulate error no faster than the longest chain allows, yielding both simpler analysis and tighter bounds than the prior characterization.

What carries the argument

Generalization of Karger's contraction algorithm to set systems, in which contraction probabilities are adjusted according to the chain length of the union-closure so that multiplicative error remains bounded after polynomially many steps.

Load-bearing premise

The generalization of Karger's contraction algorithm to set systems with bounded chain length preserves the necessary contraction probabilities and error bounds.

What would settle it

A concrete set system whose union-closure has small chain length yet whose every multiplicative (1±ε) sparsifier must contain more than any polynomial number of sets in k and 1/ε.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Simpler contraction-based proof that chain length controls multiplicative sparsifiability, tightening the authors' prior STOC 2025 bounds.

read the letter

The paper's main point is that chain length in the union-closure of a set family gives a clean parameter for multiplicative sparsifiability, with a simpler proof and better constants than the authors' own STOC 2025 work. They adapt Karger's contraction algorithm, extended via recent linear-algebraic versions, to show this directly and get improved weighted CSP sparsification bounds as a corollary. The analogy to VC-dimension for the additive case is explicit and helpful for organizing the multiplicative setting. The argument is presented more accessibly than before, which is a real gain if the details hold. The soft spot is the contraction step itself on union-closed families. Set contraction is less canonical than edge contraction, so the survival probabilities must be shown to carry over exactly for the multiplicative error guarantee without extra logarithmic or dependence factors. The abstract claims the generalized algorithm delivers the bounds, but any hidden correlation among surviving sets could affect the analysis. The paper appears to rely on the prior linear-algebraic extensions to handle this, yet the probability calculations still need close inspection. This is for people working on sparsification, CSP approximation, and extremal set theory. A reader who wants a tighter characterization or a cleaner proof technique for multiplicative error will get concrete value from the improved constants and the CSP corollary. The work shows clear engagement with the literature and a reproducible proof structure, so it deserves a serious referee even if the contraction details require verification. I would send it to peer review rather than desk reject.

Referee Report

1 major / 2 minor

Summary. The paper claims a simpler, more optimal characterization of multiplicative-error sparsifiability for set systems in terms of the chain length of their union-closure. It obtains this via a generalization of Karger's contraction algorithm (and its linear-algebraic extensions) that contracts sets while respecting the chain-length bound, yielding multiplicative sparsification bounds analogous to the role of VC-dimension for additive sparsification. A corollary improves weighted CSP sparsification bounds over Brakensiek-Guruswami.

Significance. If the central generalization holds, the result supplies a clean combinatorial parameter (chain length) that governs multiplicative sparsifiability and a probabilistic proof technique that may simplify future arguments in set-system approximation and learning theory. The explicit analogy to VC-dimension is conceptually useful and the CSP corollary is a concrete payoff.

major comments (1)

[main proof of the contraction algorithm and Theorem 1] The load-bearing step is the claim that the generalized contraction on the union-closure of a bounded-chain-length family preserves the exact per-set survival probabilities needed for multiplicative (rather than additive) error. Because set contraction is not canonically defined (unlike edge contraction), any hidden dependence among surviving sets could invalidate the multiplicative guarantee; this must be verified explicitly in the probability analysis.

minor comments (2)

[Definitions and notation] Clarify whether the chain-length parameter is taken with respect to the original family or its union-closure throughout the statements and proofs.
[Introduction] Add a short comparison table or paragraph contrasting the new chain-length bound with the previous Brakensiek-Guruswami parameters.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying the key probabilistic step in the contraction argument. We address the major comment below and indicate the revisions we will incorporate.

read point-by-point responses

Referee: [main proof of the contraction algorithm and Theorem 1] The load-bearing step is the claim that the generalized contraction on the union-closure of a bounded-chain-length family preserves the exact per-set survival probabilities needed for multiplicative (rather than additive) error. Because set contraction is not canonically defined (unlike edge contraction), any hidden dependence among surviving sets could invalidate the multiplicative guarantee; this must be verified explicitly in the probability analysis.

Authors: We agree that an explicit verification of per-set survival probabilities is essential for the multiplicative guarantee. In the current proof of Theorem 1, the contraction is performed on the union-closure while respecting the chain-length bound; the analysis proceeds by induction on chain length and shows that the survival probability of any fixed set S equals the target value (1 - O(1/ε² log(1/δ))) independently of other sets for the purpose of the multiplicative Chernoff bound. The chain-length restriction limits the number of sets that can interact with S during contraction, preventing hidden dependencies from altering the marginal probability. Nevertheless, to make this verification fully explicit and to forestall any ambiguity arising from the non-canonical nature of set contraction, we will insert a dedicated lemma (new Lemma 3.4) that directly computes the marginal survival probability for an arbitrary set and confirms that the dependence structure induced by the union-closure does not affect the multiplicative error bound. revision: yes

Circularity Check

0 steps flagged

Minor self-citation to coauthor's prior linear-algebraic contraction work; central chain-length characterization derived independently via generalized Karger method

full rationale

The derivation relies on generalizing Karger's contraction algorithm (SODA 1993) and its linear-algebraic extension (Khanna-Putterman-Sudan SODA 2024), with the latter cited by a coauthor. This is a standard self-citation but not load-bearing for the main result, as the paper presents a new contraction-based argument on union-closed set systems with bounded chain length to obtain the multiplicative sparsification bounds. No step reduces the target bound to a fitted parameter, self-definition, or unverified uniqueness theorem from the authors' prior work. The improvement over Brakensiek-Guruswami STOC 2025 is framed as a simpler proof, not a renaming or ansatz smuggling. The argument remains self-contained against external benchmarks like Karger's original analysis.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard combinatorial definitions of chain length and union-closure together with the correctness of a generalized contraction procedure drawn from prior algorithmic literature.

axioms (1)

domain assumption Chain length is the size of the longest ascending containment chain inside the union-closure of the set family.
This is the parameter the paper uses to govern multiplicative sparsifiability.

pith-pipeline@v0.9.0 · 5458 in / 1191 out tokens · 65683 ms · 2026-05-09T14:10:35.492684+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 2 canonical work pages

[1]

Constraint ac- quisition via partial queries

[BCH+13] Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Constraint ac- quisition via partial queries. In Francesca Rossi, editor,IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 4...

2013
[2]

Redundancy is all you need

[BG25] Joshua Brakensiek and Venkatesan Guruswami. Redundancy is all you need. In Michal Kouck´ y and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1614–1625. ACM,

2025
[3]

In Gary L

time. In Gary L. Miller, editor,Proceedings of the Twenty-Eighth Annual ACM Sym- posium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55. ACM,

1996
[4]

Kothari, Yang P

[BKLM26] Arpon Basu, Pravesh K. Kothari, Yang P. Liu, and Raghu Meka. Sparsifying sums of positive semidefinite matrices. In Kasper Green Larsen and Barna Saha, editors,Pro- ceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6042–6064. SIAM,

2026
[5]

Batson, Daniel A

[BSS09] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. In Michael Mitzenmacher, editor,Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 255–262. ACM,

2009
[6]

Near-linear size hypergraph cut sparsi- fiers

[CKN20] Yu Chen, Sanjeev Khanna, and Ansh Nagda. Near-linear size hypergraph cut sparsi- fiers. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Com- puter Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 61–72. IEEE,

2020
[7]

A constant lower bound for the union-closed sets conjecture.arXiv preprint arXiv:2211.09055,

[Gil22] Justin Gilmer. A constant lower bound for the union-closed sets conjecture.arXiv preprint arXiv:2211.09055,

work page arXiv
[8]

Karger, and Debmalya Panigrahi

[GKP17] Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi. Random contractions and sampling for hypergraph and hedge connectivity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Al- gorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1101–1114. SIAM,

2017
[9]

Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang

[HLM+26] Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang. Sparsifying cayley graphs on every group. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6029–

2026
[10]

[Kar93] David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min- cut algorithm. In Vijaya Ramachandran, editor,Proceedings of the Fourth An- nual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 21–30. ACM/SIAM,

1993
[11]

Sketching cuts in graphs and hypergraphs

[KK15] Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Tim Roughgarden, editor,Proceedings of the 2015 Conference on Innovations in The- oretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 367–376. ACM,

2015
[12]

Spectral hypergraph sparsifiers of nearly linear size

[KKTY21a] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1159–1170. IEEE,

2021
[13]

Code sparsification and its applications

[KPS24b] Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Code sparsification and its applications. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 5145–5168. SIAM,

2024
[14]

Efficient algorithms and new characterizations for CSP sparsification

[KPS25a] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Efficient algorithms and new characterizations for CSP sparsification. In Michal Kouck´ y and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 407–416. ACM,

2025
[15]

A theory of spectral CSP sparsification.arXiv preprint arXiv:2504.16206,

[KPS25b] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. A theory of spectral CSP sparsification.arXiv preprint arXiv:2504.16206,

work page arXiv
[16]

[Lee23] James R. Lee. Spectral hypergraph sparsification via chaining. In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on The- ory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 207–218. ACM,

2023

[1] [1]

Constraint ac- quisition via partial queries

[BCH+13] Christian Bessiere, Remi Coletta, Emmanuel Hebrard, George Katsirelos, Nadjib Lazaar, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. Constraint ac- quisition via partial queries. In Francesca Rossi, editor,IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pages 4...

2013

[2] [2]

Redundancy is all you need

[BG25] Joshua Brakensiek and Venkatesan Guruswami. Redundancy is all you need. In Michal Kouck´ y and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1614–1625. ACM,

2025

[3] [3]

In Gary L

time. In Gary L. Miller, editor,Proceedings of the Twenty-Eighth Annual ACM Sym- posium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 47–55. ACM,

1996

[4] [4]

Kothari, Yang P

[BKLM26] Arpon Basu, Pravesh K. Kothari, Yang P. Liu, and Raghu Meka. Sparsifying sums of positive semidefinite matrices. In Kasper Green Larsen and Barna Saha, editors,Pro- ceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6042–6064. SIAM,

2026

[5] [5]

Batson, Daniel A

[BSS09] Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice-Ramanujan sparsifiers. In Michael Mitzenmacher, editor,Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 255–262. ACM,

2009

[6] [6]

Near-linear size hypergraph cut sparsi- fiers

[CKN20] Yu Chen, Sanjeev Khanna, and Ansh Nagda. Near-linear size hypergraph cut sparsi- fiers. In Sandy Irani, editor,61st IEEE Annual Symposium on Foundations of Com- puter Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 61–72. IEEE,

2020

[7] [7]

A constant lower bound for the union-closed sets conjecture.arXiv preprint arXiv:2211.09055,

[Gil22] Justin Gilmer. A constant lower bound for the union-closed sets conjecture.arXiv preprint arXiv:2211.09055,

work page arXiv

[8] [8]

Karger, and Debmalya Panigrahi

[GKP17] Mohsen Ghaffari, David R. Karger, and Debmalya Panigrahi. Random contractions and sampling for hypergraph and hedge connectivity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Al- gorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1101–1114. SIAM,

2017

[9] [9]

Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang

[HLM+26] Jun-Ting Hsieh, Daniel Z. Lee, Sidhanth Mohanty, Aaron Putterman, and Rachel Yun Zhang. Sparsifying cayley graphs on every group. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 6029–

2026

[10] [10]

[Kar93] David R. Karger. Global min-cuts in rnc, and other ramifications of a simple min- cut algorithm. In Vijaya Ramachandran, editor,Proceedings of the Fourth An- nual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 21–30. ACM/SIAM,

1993

[11] [11]

Sketching cuts in graphs and hypergraphs

[KK15] Dmitry Kogan and Robert Krauthgamer. Sketching cuts in graphs and hypergraphs. In Tim Roughgarden, editor,Proceedings of the 2015 Conference on Innovations in The- oretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 367–376. ACM,

2015

[12] [12]

Spectral hypergraph sparsifiers of nearly linear size

[KKTY21a] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1159–1170. IEEE,

2021

[13] [13]

Code sparsification and its applications

[KPS24b] Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Code sparsification and its applications. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 5145–5168. SIAM,

2024

[14] [14]

Efficient algorithms and new characterizations for CSP sparsification

[KPS25a] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. Efficient algorithms and new characterizations for CSP sparsification. In Michal Kouck´ y and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 407–416. ACM,

2025

[15] [15]

A theory of spectral CSP sparsification.arXiv preprint arXiv:2504.16206,

[KPS25b] Sanjeev Khanna, Aaron Putterman, and Madhu Sudan. A theory of spectral CSP sparsification.arXiv preprint arXiv:2504.16206,

work page arXiv

[16] [16]

[Lee23] James R. Lee. Spectral hypergraph sparsification via chaining. In Barna Saha and Rocco A. Servedio, editors,Proceedings of the 55th Annual ACM Symposium on The- ory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 207–218. ACM,

2023