arxiv: 2605.08676 · v1 · submitted 2026-05-09 · 🧮 math.CO

Recognition: 2 theorem links

· Lean Theorem

Moonflowers and efficient code sparsification

Raghu Meka, Shachar Lovett, Yimeng Wang

Pith reviewed 2026-05-12 00:50 UTC · model grok-4.3

classification 🧮 math.CO

keywords moonflowerssunflowersextremal set theorycode sparsificationforbidden configurationsset familiescombinatorial bounds

0 comments

The pith

Moonflowers, a relaxed sunflower, give near-optimal bounds on moonflower-free set families and reduce code sparsification to logarithmic block-length dependence.

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

The paper introduces moonflowers as k-tuples of sets where each set contains at least one element absent from the rest. It determines the maximum size of a family of w-sized sets that avoids a k-moonflower and establishes bounds that are tight up to lower-order terms. This extremal result is applied to code sparsification, where the overhead depending on block length improves from polylogarithmic to logarithmic, with a matching lower bound proving necessity. A sympathetic reader cares because these tighter bounds yield more efficient algorithms for sparsifying large codes while preserving key properties. The work shows that moonflowers isolate the right combinatorial obstruction for both the set-family problem and its algorithmic application.

Core claim

The central claim is that the largest family of sets of size at most w without a k-moonflower has size governed by near-optimal bounds that match known constructions up to constant factors; applying the same combinatorial control to code sparsification produces algorithms whose dependence on block length improves from poly-logarithmic to logarithmic, and this logarithmic dependence is necessary.

What carries the argument

The moonflower, a k-tuple of sets in which each member has a private element not appearing in any other member of the tuple, which functions as the minimal forbidden configuration whose absence limits family growth and directly supplies the quantitative control needed for sparsification.

If this is right

Moonflower-free families of w-sets can be as large as the near-optimal upper bound permits.
Code sparsification now incurs only a logarithmic factor in block length rather than a polylogarithmic one.
The logarithmic dependence on block length cannot be removed, as matching lower bounds exist.
The same moonflower avoidance technique supplies quantitative control for related problems in extremal set theory.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Moonflowers may serve as a template for defining other relaxed forbidden configurations that tighten bounds in intersecting-family problems.
The logarithmic improvement could be tested empirically by implementing the new sparsifier on concrete code instances with varying block lengths.
Similar private-element arguments might extend to hypergraph coloring or property testing settings where unique witnesses control complexity.

Load-bearing premise

The combinatorial arguments establishing the near-optimality of the moonflower bounds and the necessity of the logarithmic dependence in code sparsification hold without hidden restrictions on the parameters w and k.

What would settle it

A concrete falsifier is an explicit construction of more than the claimed number of w-sized sets that still avoids any k-moonflower, or a sparsification procedure that succeeds with o(log n) dependence on block length for arbitrary block lengths.

read the original abstract

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.

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

Moonflowers give a clean logarithmic improvement on code sparsification bounds plus a necessity result, but the proofs need checking for hidden restrictions on w and k.

read the letter

The paper defines a k-moonflower as a family of sets where each one has an element missing from all the others. It then bounds the maximum size of a w-uniform family without such a moonflower and applies the bound to improve code sparsification. The main payoff is replacing the poly-log dependence on block length from Brakensiek-Guruswami with a plain log factor, plus a matching lower bound showing the log is required. That is the concrete advance worth noting first. The definition itself is simple and sits between the classical sunflower and weaker notions people have tried, so the extremal result feels like a natural next step rather than a forced construction. The application reuses the same counting ideas to get the algorithmic gain without extra machinery. That part is done cleanly. The soft spot is exactly the one the stress-test flags. The near-optimality and the necessity claim both rest on combinatorial arguments whose range of validity is not spelled out in the abstract. If those arguments only go through when w is at least logarithmic in k, or when k is not too large relative to 2^w, then the claimed improvement and the necessity statement would not hold in the full parameter space that matters for sparsification. The paper does not appear to flag any such cutoff, so a referee will want to see the precise statements and the edge-case handling. Nothing in the abstract suggests circularity or invented parameters, and the citation to the prior STOC paper is direct. Readers who work on extremal set theory or on derandomization and sparsification techniques will find the new bound useful. It is the sort of paper that deserves a serious referee: the improvement is modest but explicit, the necessity result adds value, and the only real question is whether the proofs cover the regimes the abstract claims. I would send it to review rather than desk-reject.

Referee Report

1 major / 3 minor

Summary. The paper introduces moonflowers as a weaker analogue of sunflowers: a k-moonflower is a family of k sets in which each set contains at least one element absent from all the others. It determines the maximum size of a family of sets of size at most w that avoids a k-moonflower and obtains near-optimal upper and lower bounds. These combinatorial results are then applied to the code-sparsification problem of Brakensiek and Guruswami (STOC 2025), improving the dependence on block length from poly-logarithmic to logarithmic and proving that a logarithmic dependence is necessary.

Significance. If the claimed near-optimality holds, the work strengthens extremal set theory by introducing a natural weakening of the sunflower lemma with matching bounds. The code-sparsification application supplies a concrete improvement with an accompanying necessity argument, which is a positive feature. The manuscript does not appear to rely on fitted parameters or self-referential equations.

major comments (1)

[§4] §4, Theorem 4.3 (necessity of logarithmic dependence): the argument that any sparsifier must incur a log factor in the block length appears to rest on a counting argument over the possible supports; it would be helpful to confirm explicitly that the construction works for all w, k in the regime of interest for code sparsification (including when w = o(log k)) rather than implicitly assuming w = Ω(log k).

minor comments (3)

[§2] The definition of moonflower in §2 is clear, but the notation for the extremal function (e.g., ex(w,k)) should be introduced once and used consistently in all subsequent statements.
[Figure 1] Figure 1 (illustration of a 3-moonflower) would benefit from an explicit caption stating the unique elements.
[§5] In the application section, the reduction from code sparsification to moonflower-free families is sketched but the precise parameter mapping (how w and k translate to block length and sparsity) could be stated as a lemma for clarity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comment. We address the major comment below and have incorporated a clarification into the revised version.

read point-by-point responses

Referee: [§4] §4, Theorem 4.3 (necessity of logarithmic dependence): the argument that any sparsifier must incur a log factor in the block length appears to rest on a counting argument over the possible supports; it would be helpful to confirm explicitly that the construction works for all w, k in the regime of interest for code sparsification (including when w = o(log k)) rather than implicitly assuming w = Ω(log k).

Authors: We appreciate the referee's suggestion to make the scope of the lower bound explicit. The counting argument in the proof of Theorem 4.3 enumerates the possible supports of size at most w and does not invoke any assumption relating w to k (such as w = Ω(log k)). The same argument applies verbatim for all w, k ≥ 2, including the regime w = o(log k) that arises in certain code-sparsification settings. To address the request, we have inserted a short remark immediately after the statement of Theorem 4.3 confirming that the lower bound holds uniformly over the full parameter range relevant to the application. revision: yes

Circularity Check

0 steps flagged

No circularity detected in moonflower definition, extremal bounds, or sparsification application

full rationale

The paper introduces moonflowers via an explicit definition (each set has a unique element absent from the others), then derives near-optimal extremal bounds on families of w-sized sets avoiding k-moonflowers through direct combinatorial arguments. These bounds are applied to improve code sparsification dependence on block length from poly-log to log, with necessity also shown combinatorially. No equations or steps reduce by construction to prior fitted values, self-definitions, or self-citations; the chain is self-contained with independent content from the new object and arguments. The cited prior work (Brakensiek-Guruswami) is external and does not create a load-bearing self-reference chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on the new definition of moonflowers and standard counting arguments in extremal set theory; no free parameters or invented physical entities are introduced.

axioms (1)

standard math Standard axioms of set theory and finite combinatorics
Used to define families of sets and the moonflower property.

invented entities (1)

moonflower no independent evidence
purpose: Weaker analogue of sunflower for extremal problems
Newly defined combinatorial object introduced to obtain improved bounds.

pith-pipeline@v0.9.0 · 5427 in / 1205 out tokens · 49632 ms · 2026-05-12T00:50:33.906141+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
Theorem 1.4 (Extremal bounds on moonflowers) ... |F| ≤ (C·k/w)^w if w≤k ... via iterative puncturing and (p,M)-almost-covered families
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
Lemma 3.5 (Moonflower⇒small VC of union-closure) ... VC(U(F))≤k−1

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

[1]

2025 , isbn =

Brakensiek, Joshua and Guruswami, Venkatesan , title =. 2025 , isbn =. doi:10.1145/3717823.3718212 , booktitle =

work page doi:10.1145/3717823.3718212 2025
[2]

Optimization Under Unknown Constraints

Boucheron, Stéphane and Lugosi, Gábor and Massart, Pascal , title =. 2013 , month =. doi:10.1093/acprof:oso/9780199535255.001.0001 , url =

work page doi:10.1093/acprof:oso/9780199535255.001.0001 2013
[3]

2005 , publisher =

Probability and Computing: Randomized Algorithms and Probabilistic Analysis , author =. 2005 , publisher =

work page 2005
[4]

Discrete Mathematics , volume =

Induced matchings in bipartite graphs , author =. Discrete Mathematics , volume =. 1989 , doi =

work page 1989
[5]

2022 , eprint=

A constant lower bound for the union-closed sets conjecture , author=. 2022 , eprint=

work page 2022
[6]

2023 , eprint=

An improved lower bound for the union-closed set conjecture , author=. 2023 , eprint=

work page 2023
[7]

, title =

Sauer, N. , title =. Journal of Combinatorial Theory, Series A , volume =. 1972 , month = jul, doi =

work page 1972
[8]

Pacific Journal of Mathematics , volume =

Shelah, Saharon , title =. Pacific Journal of Mathematics , volume =. 1972 , month = apr, doi =

work page 1972
[9]

Mathematische Annalen , year =

Neumann, John , title =. Mathematische Annalen , year =

work page
[10]

Proceedings of the 2024

Sanjeev Khanna and Aaron (Louie) Putterman and Madhu Sudan , title =. Proceedings of the 2024. 2024 , doi =

work page 2024
[11]

2025 , isbn =

Khanna, Sanjeev and Putterman, Aaron and Sudan, Madhu , title =. 2025 , isbn =. doi:10.1145/3717823.3718205 , booktitle =

work page doi:10.1145/3717823.3718205 2025
[12]

Intersection theorems for systems of sets , journal =

Erd. Intersection theorems for systems of sets , journal =

work page
[13]

Kostochka, A. V. , title =. The Mathematics of Paul Erd. 1997 , doi =

work page 1997
[14]

2018 , url =

Fukuyama, Junichiro , title =. 2018 , url =. 1809.10318 , archivePrefix=

work page arXiv 2018
[15]

Annals of Mathematics , volume =

Alweiss, Ryan and Lovett, Shachar and Wu, Kewen and Zhang, Jiapeng , title =. Annals of Mathematics , volume =. 2021 , doi =

work page 2021
[16]

Combinatorics, Probability and Computing , volume =

Kahn, Jeff and Kalai, Gil , title =. Combinatorics, Probability and Computing , volume =. 2007 , month =. doi:10.1017/S0963548307008474 , publisher =

work page doi:10.1017/s0963548307008474 2007
[17]

Journal of the American Mathematical Society , volume =

Park, Jinyoung and Pham, Huy Tuan , title =. Journal of the American Mathematical Society , volume =. 2024 , pages =. doi:10.1090/jams/1028 , url =

work page doi:10.1090/jams/1028 2024
[18]

SIAM Journal on Computing , year =

Rossman, Benjamin , title =. SIAM Journal on Computing , year =

work page
[19]

Algorithmica , volume =

Bruno Pasqualotto Cavalar and Mrinal Kumar and Benjamin Rossman , title =. Algorithmica , volume =. 2022 , doi =

work page 2022
[20]

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages =

Lovett, Shachar and Meka, Raghu and Mertz, Ian and Pitassi, Toniann and Zhang, Jiapeng , title =. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , pages =. 2022 , publisher =. doi:10.4230/LIPIcs.ITCS.2022.104 , isbn =

work page doi:10.4230/lipics.itcs.2022.104 2022
[21]

Discrete Analysis , year =

Anup Rao , title =. Discrete Analysis , year =

work page
[22]

Discrete Mathematics , volume =

Tolson Bell and Suchakree Chueluecha and Lutz Warnke , title =. Discrete Mathematics , volume =

work page