Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.08676 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915997365043200 |
|---|---|
| author | Lovett, Shachar Meka, Raghu Wang, Yimeng |
| author_facet | Lovett, Shachar Meka, Raghu Wang, Yimeng |
| contents | We introduce \emph{moonflowers}, a weaker analogue of sunflowers. A family of sets $S_1,\ldots,S_k$ is a $k$-moonflower if each set $S_i$ contains at least one element that is absent from all the others. We study the extremal problem of determining the largest possible size of a family of sets of size at most $w$ that avoids a $k$-moonflower, and obtain near-optimal bounds.
As an application, we revisit the code sparsification problem studied by Brakensiek and Guruswami (STOC 2025) and improve the bounds to near optimal. Concretely, we improve the dependence on the block length from poly-logarithmic to logarithmic, and show that such a dependence is necessary. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_08676 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Moonflowers and efficient code sparsification Lovett, Shachar Meka, Raghu Wang, Yimeng Combinatorics 68P30, 05D10 We introduce \emph{moonflowers}, a weaker analogue of sunflowers. A family of sets $S_1,\ldots,S_k$ is a $k$-moonflower if each set $S_i$ contains at least one element that is absent from all the others. We study the extremal problem of determining the largest possible size of a family of sets of size at most $w$ that avoids a $k$-moonflower, and obtain near-optimal bounds. As an application, we revisit the code sparsification problem studied by Brakensiek and Guruswami (STOC 2025) and improve the bounds to near optimal. Concretely, we improve the dependence on the block length from poly-logarithmic to logarithmic, and show that such a dependence is necessary. |
| title | Moonflowers and efficient code sparsification |
| topic | Combinatorics 68P30, 05D10 |
| url | https://arxiv.org/abs/2605.08676 |