The Reach of Abelian Covers in Hypergraphs
Abstract
Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges. For example, even covers--which check if each vertex appears in an even number of hyperedges--have found much success recently in the study of locally decodable codes. Inspired by a recently-emerging line of work on the non-redundancy of constraint satisfaction problems (CSPs), we introduce and study two novel families of covers of hypergraphs which are stricter than even covers: \emph{Abelian} covers and Catalan covers. Abelian covers are similar to even covers, except that arithmetic is now done over the integers rather than modulo 2, allowing us to capture dependences over arbitrary Abelian groups. Catalan covers capture the behavior of non-Abelian groups by only allowing local cancellations in a sequence of hyperedges. We prove three main results about Abelian and Catalan covers. First, using tools from lattice theory, we show that any r-uniform hypergraph with n vertices and n log(r) hyperedges has an Abelian cover. Second, using tools from algebraic topology, we show that in any $3$-uniform hypergraph, Abelian covers and Catalan covers are equivalent; thereby showing that Catalan covers emerge after O(n) hyperedges in $3$-uniform hypergraphs. Finally, using the theory of nilpotent groups, we show that there exists a $4$-uniform hypergraph which has an Abelian cover but not a Catalan cover. Collectively, these results exactly characterize the reach that Abelian covers have in deducing dependences in hypergraphs. As our primary application, we show that any arity-$3$ CSP with an infinite-domain Mal'tsev extension has linear non-redundancy. This implies near optimal streaming, sparsification, and kernelization algorithms for this family of CSPs. Previously, such a result was only known for the much simpler case of arity-$2$ CSPs.
Related
- Projective dimension of closed neighborhood hypergraphs via extended double covers
- Abelian surfaces of small conductor from genus 3 double covers
- Eventual Exactness and Rigidity for Abelian Covers of Groups
- A Global Generic Locus for Elementary Abelian p-covers of P^1 with two Ramification Points
- Abelian canonical covers of minimal rational surfaces and 𝔽1 up to degree $8$
BibTeX
@misc{brakensiek2026reach,
title = {{The Reach of Abelian Covers in Hypergraphs}},
author = {Joshua Brakensiek and Venkatesan Guruswami and Aaron Putterman},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36761},
eprint = {2609.36761},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36761},
}
RIS
TY - UNPB
TI - The Reach of Abelian Covers in Hypergraphs
AU - Joshua Brakensiek
AU - Venkatesan Guruswami
AU - Aaron Putterman
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36761
UR - https://arxiv.org/abs/2609.36761
AB - Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges. For example, even covers--which check if each vertex appears in an even number of hyperedges--have found much success recently in the study of locally decodable codes. Inspired by a recently-emerging line of work on the non-redundancy of constraint satisfaction problems (CSPs), we introduce and study two novel families of covers of hypergraphs which are stricter than even covers: \emph{Abelian} covers and Catalan covers. Abelian covers are similar to even covers, except that arithmetic is now done over the integers rather than modulo 2, allowing us to capture dependences over arbitrary Abelian groups. Catalan covers capture the behavior of non-Abelian groups by only allowing local cancellations in a sequence of hyperedges. We prove three main results about Abelian and Catalan covers. First, using tools from lattice theory, we show that any r-uniform hypergraph with n vertices and n log(r) hyperedges has an Abelian cover. Second, using tools from algebraic topology, we show that in any $3$-uniform hypergraph, Abelian covers and Catalan covers are equivalent; thereby showing that Catalan covers emerge after O(n) hyperedges in $3$-uniform hypergraphs. Finally, using the theory of nilpotent groups, we show that there exists a $4$-uniform hypergraph which has an Abelian cover but not a Catalan cover. Collectively, these results exactly characterize the reach that Abelian covers have in deducing dependences in hypergraphs. As our primary application, we show that any arity-$3$ CSP with an infinite-domain Mal'tsev extension has linear non-redundancy. This implies near optimal streaming, sparsification, and kernelization algorithms for this family of CSPs. Previously, such a result was only known for the much simpler case of arity-$2$ CSPs.
ER -