Metraipolis › archive › dc_3893687f509f
The Reach of Abelian Covers in Hypergraphs — arXiv:2609.36761
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.36761
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:34:01.882Z
- SHA-256 of the archived text
ece726eaa7bf8230269e8ba7d4b55e5d7b229c69aa661e6f8d0b3fbd78dc1f6b- Stable URL of this page
https://metraipolis.com/documento/dc_3893687f509f
How to cite
The Reach of Abelian Covers in Hypergraphs — arXiv:2609.36761 — arXiv (en), https://arxiv.org/abs/2609.36761 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3893687f509f (Metraipolis archive dc_3893687f509f, sha256 ece726eaa7bf8230269e8ba7d4b55e5d7b229c69aa661e6f8d0b3fbd78dc1f6b)
BibTeX
@misc{dc3893687f509f,
title = {The Reach of Abelian Covers in Hypergraphs — arXiv:2609.36761},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.36761},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3893687f509f; sha256 ece726eaa7bf8230269e8ba7d4b55e5d7b229c69aa661e6f8d0b3fbd78dc1f6b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.36761. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.36761 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T17:59:19.289Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).