Δ-system / sunflower — the core combinatorial object

Statement

Definition (Δ-system / sunflower). A family of sets $A_1,\dots,A_r$ is a Δ-system with $r$ petals (equivalently, a sunflower of size $r$) if there is a fixed set $Y$ (the core or kernel) such that $$ A_i \cap A_j = Y \quad\text{for all } i\neq j. $$ The sets $A_i\setminus Y$ (the petals) are pairwise disjoint (allowed to be empty, which degenerates to a family of pairwise-disjoint sets, $Y=\varnothing$). (Source: en.wikipedia.org/wiki/Sunflower_(mathematics).)

The Erdős–Rado sunflower lemma (finite form, 1960). For integers $k,r\ge1$, let $f(k,r)$ be the smallest integer such that every family $\mathcal F$ of sets of size $\le k$ with $|\mathcal F| > f(k,r)$ contains a Δ-system with $r$ petals. Then $$ f(k,r) \;\le\; k!\,(r-1)^k. $$ Equivalently: any family of more than $k!(r-1)^k$ sets, each of size at most $k$, contains an $r$-sunflower. (Erdős–Rado, "Intersection theorems for systems of sets," J. London Math. Soc. 35 (1960); restated e.g. in Wikipedia's Sunflower(mathematics) article and Kupavskii's survey, arXiv:2508.20132.)

The (still open) Erdős–Rado sunflower conjecture. For each fixed $r\ge3$, is $f(k,r) \le C_r^{\,k}$ for some constant $C_r$ depending only on $r$ (not on $k$)? I.e. can the $k!$ factor be removed entirely, leaving a bound *exponential* in $k$ rather than the classical bound's much larger $k^{k(1+o(1))}$ growth? Erdős specifically offered \$1000 for the case $r=3$ alone, which he believed "contains the whole difficulty." This is Erdős #20 — sunflower conjecture, exponential bound for f(n,k) on erdosproblems.com, confirmed open as of the current search. (Source: this wiki's Erdős #20 — sunflower conjecture, exponential bound for f(n,k), itself verified against erdosproblems.com/20 directly.)

Infinite/set-theoretic form (Δ-system lemma). In infinite combinatorics (set theory / forcing), the classical statement is: *every uncountable family of finite sets has an uncountable Δ-subsystem.* More generally, for a regular uncountable cardinal $\kappa$ with $\lambda^{<\omega}<\kappa$ for all $\lambda<\kappa$ (true e.g. for $\kappa=\aleph_1$ unconditionally, and — under GCH — for a much wider class of regular $\kappa$), every family of $\kappa$-many finite sets contains a Δ-subsystem of size $\kappa$. (Source: WebSearch corroboration of the standard statement as in Jech, *Set Theory*, and Kunen; see also cs.famaf.unc.edu.ar/~pedro/Delta_System_Lemma notes and dantopology.wordpress.com — secondary sources, not directly fetched here.)

Facts

- Origin. Erdős and Rado, "Intersection theorems for systems of sets," *J. London Math. Soc.* 35 (1960), 85–90 — the paper that introduced Δ-systems and proved the finite lemma above; the name "sunflower" is a later, more visual synonym (kernel = disc, petals = the non-overlapping "leaves" arranged around it). (Wikipedia; Kupavskii survey.) - Tightness of the exponent in $r$, looseness in $k$. The bound $k!(r-1)^k$ is essentially sharp in its dependence on $r$ (a simple product/coloring construction — take all functions $f:[k]\to[r-1]$ and let $A_f=\{(x,f(x)):x\in[k]\}$ — gives $(r-1)^k$ sets with no $r$-sunflower), but the $k!$ (equivalently $k^{k(1+o(1))}$) dependence on $k$ is widely believed *not* to be necessary — this gap is exactly the content of the open sunflower conjecture Erdős #20 — sunflower conjecture, exponential bound for f(n,k). (Source: erdosproblems/20.md in this wiki, itself citing thomasbloom.org/notes/sunflowers.html.) - Modern bound-improvement chain (all attacking the sunflower conjecture, i.e. removing the $k!$/superexponential factor): Spencer (1970s) → Kostochka (1997), shaving a $\log\log k/\log k$-type factor off the classical bound, the record for over 20 years → Alweiss, Lovett, Wu, Zhang (2019/2020), arXiv:1908.08483, STOC 2020: first bound of shape $(\text{polylog }k)^k$ — a genuine breakthrough — via the robust/spread-sunflower technique → Rao (2020), arXiv:1909.04774, an independent entropy/coding-theoretic reproof within about a month → Frankston–Kahn–Narayanan–Park (2019/2021), arXiv:1910.13433, deriving a comparable bound as a corollary of proving Talagrand's fractional expectation-threshold conjecture → Bell–Chueluecha–Warnke (2021), tightening to $(O(r\log k))^k$, the best *general* bound as of this search. (Fully sourced with exact statements and dates in this wiki's Erdős #20 — sunflower conjecture, exponential bound for f(n,k) and R-spread set families (ALWZ/Rao's central reduction device).) - The conjecture is still open even for $r=3$ (the case Erdős's \$1000 targeted): the gap between the $(r-1)^k$ lower-bound construction and the $(O(r\log k))^k$ upper bound is exactly one $\log k$ factor, unclosed as of this search. (Source: Erdős #20 — sunflower conjecture, exponential bound for f(n,k).) - Deza–Erdős–Frankl and the "Δ-system method." The technique of *deliberately extracting a Δ-system from an extremal family and analyzing its core* — as opposed to merely proving sunflowers exist — was developed by Deza, Erdős and Frankl for $(n,k,L)$-systems: families of $k$-sets on $[n]$ whose pairwise intersection sizes all lie in a fixed set $L\subset\{0,\dots,k-1\}$. This "Δ-system method" was systematized and extended by Frankl and Füredi (1980s) into a general tool for extremal set theory, and is distinct from (though built on) the sunflower *lemma* itself — hence it gets its own survey, Kupavskii, "Delta-system method: a survey," arXiv:2508.20132 (2025), covering results "from the classical Deza–Erdős–Frankl and Frankl–Füredi papers to modern applications." (Source: arXiv:2508.20132, full HTML read.) - Re-proving Frankl–Wilson via the Δ-system method. The Δ-system method gives an alternative (if slightly weaker-constant) proof route to the celebrated Frankl–Wilson modular intersection theorem ("if $p$ is prime, $N(4p,2p,p)\le 2\binom{4p}{p-1}$" — forbidding one single intersection size collapses family size exponentially), by combining a Δ-system extraction step with Turán's theorem on the "link" structure. (Source: WebSearch corroboration of Kupavskii's survey content.) - **Naslund–Sawin's cap-set-method sunflower bound is a *different* (weaker-uniformity) sunflower question**, not the same as Erdős #20 — sunflower conjecture, exponential bound for f(n,k): it bounds 3-sunflower-free families of *arbitrary* (non-uniform) subsets of $[n]$ by $\approx 1.89^n$ via the polynomial/slice-rank method (arXiv:1606.09575) — already fully documented in this wiki's Cap-set problem — max progression-free subset of F_3^n — showing the *weak* Erdős–Szemerédi sunflower conjecture is resolved even though the uniform Erdős–Rado version Erdős #20 — sunflower conjecture, exponential bound for f(n,k) is not. - Infinite-combinatorics use: the Δ-system lemma in forcing. In set theory, the Δ-system lemma is the standard tool for proving a forcing notion (partial order) is ccc (countable chain condition): given an uncountable set of conditions (each built from finitely much information), extract an uncountable Δ-subsystem; conditions sharing the same core but disjoint petals are then shown compatible by a case analysis on the petals alone, ruling out an uncountable antichain. ccc-ness in turn guarantees forcing preserves cardinals — a load-bearing step in essentially every classical forcing consistency proof (e.g. via finite-support ccc iterations for Martin's Axiom). (WebSearch corroboration of the standard textbook statement, e.g. Jech's *Set Theory*, Kunen's *Set Theory*; not independently re-derived here.) - TCS applications: DNF sparsification and circuit lower bounds. "Robust sunflowers" (a strengthened, quantitative Δ-system notion used by Rossman and by Alweiss–Lovett–Wu–Zhang) connect Δ-systems to DNF-formula sparsification and monotone circuit lower bounds (e.g. for $k$-clique on random graphs): a DNF/decision-tree-like object containing a large robust sunflower can be replaced by a simpler equivalent object under random restriction, which is exactly the combinatorial core of several switching-lemma-style circuit lower bound arguments. (Source: arXiv:1908.08483 §1.1, cross-checked against this wiki's R-spread set families (ALWZ/Rao's central reduction device).) - Matrix-multiplication connection. A sufficiently strong *balanced* form of the sunflower conjecture (roughly: $f(k,r)\le (r-1)^k$ for balanced/colored families, with $k=O(\log n)$) is known to imply essentially quadratic-time matrix multiplication algorithms, via the Cohn–Umans group-theoretic approach to fast matrix multiplication; this is one of the main reasons the sunflower conjecture is treated as a flagship target rather than a curiosity. (Source: gilkalai.wordpress.com/2015/11/03/polymath10-the-erdos-rado-delta-system-conjecture, direct fetch.)

Technique

When to use the Δ-system/sunflower lemma. Whenever a combinatorial argument needs to go from "the family is merely *large*" to "the family contains *highly structured, pairwise-uniform* members" — because uniform pairwise intersections are enormously easier to reason about than arbitrary intersection patterns. Typical trigger: you have a family of bounded-size sets (or, in the infinite setting, a family of finite "conditions"/"supports") that is too big to handle case-by-case, and you want to reduce to a sub-family where all pairwise interactions are literally identical.

The classical extraction argument (why the finite lemma is true), step by step — induction on $k$ (set size), from extremalcombinatorics.com's presentation, cross-checked: 1. Base case $k=1$. Any $\ge r$ distinct singletons trivially form an $r$-sunflower with empty core (they're pairwise disjoint). 2. Inductive step, given $|\mathcal F| > k!(r-1)^k$ sets of size $\le k$. Greedily build a maximal collection $\mathcal A$ of pairwise-disjoint sets from $\mathcal F$. - If $|\mathcal A|\ge r$: done — a maximal disjoint sub-collection *is* a sunflower with empty core. - If $|\mathcal A| < r$: by maximality, every set in $\mathcal F$ meets $X=\bigcup\mathcal A$, and $|X|\le (r-1)k$. By pigeonhole, some single element $x\in X$ lies in more than $|\mathcal F|/|X| > k!(r-1)^k / ((r-1)k) = (k-1)!(r-1)^{k-1}$ sets of $\mathcal F$. 3. Recurse. Let $\mathcal F' = \{A\setminus\{x\} : x\in A\in\mathcal F\}$ restricted to those $>(k-1)!(r-1)^{k-1}$ sets containing $x$; these have size $\le k-1$ and exceed the inductive threshold, so by the induction hypothesis $\mathcal F'$ contains an $r$-sunflower. Adding $x$ back to every set (and to the core) turns it into an $r$-sunflower inside the original $\mathcal F$.

Why it works, in one sentence

*either* the family already contains a large disjoint (i.e. empty-core sunflower) sub-collection, *or* it must be so densely "clustered" around a bounded union $X$ that pigeonhole forces some single element into super-linearly many sets — and peeling that element off strictly shrinks the problem while preserving (rescaled) the counting threshold, so the argument terminates by induction on set size. This "disjoint-or-clustered" dichotomy is the direct 1960s ancestor of the modern "spread-or-reducible" dichotomy used by ALWZ/Rao (see R-spread set families (ALWZ/Rao's central reduction device)) to get the vastly better $(\text{polylog }k)^k$ bound — the classical proof peels off one popular element at a time; the modern proof instead certifies that *no* small pattern is over-represented (spreadness) and then uses a probabilistic/entropy hitting argument in one shot, avoiding the $k!$-type blow-up from repeated worst-case pigeonholing.

How to actually deploy a Δ-system in a proof (the "Δ-system method" of Deza–Erdős–Frankl / Frankl–Füredi): 1. Take your extremal family $\mathcal F$ of $k$-sets (e.g. one avoiding a forbidden configuration, or one you're trying to upper-bound the size of). 2. If $|\mathcal F|$ is large enough, invoke the sunflower lemma to extract a sub-family that is itself a large Δ-system with some core $Y$, $|Y|=y<k$. 3. Analyze the petals (the sets minus the core, which are pairwise disjoint $(k-y)$-sets) as a *simpler*, lower-dimensional combinatorial object — often reducing an intersection-pattern question on $k$-sets to a question on disjoint $(k-y)$-sets, or combining with a separate tool (e.g. Turán's theorem, as in the Deza–Erdős–Frankl route to Frankl–Wilson) applied to the link/petal structure. 4. Iterate/recurse across different possible core sizes $y$ if needed, and glue bounds back together — this is the standard shape of Deza–Erdős–Frankl-style $(n,k,L)$-system theorems and their descendants (Kupavskii's survey, arXiv:2508.20132, catalogs many such applications: Turán-type problems for hypergraph expansions, forbidden simplices/trees, $d$-wise intersecting families). 5. In the infinite setting, the same "extract a Δ-subsystem, then reason only about disjoint petals" pattern proves ccc-ness of a forcing poset (§Facts above) — the sunflower lemma is what converts "uncountably many finite-support conditions" into "countably-generated compatibility classes."

Recombination hooks. Any Erdős-problem-shaped question of the form "a family of bounded-size sets larger than $X$ must contain structure $S$" is a candidate for either (a) the *classical* sunflower lemma directly, when a crude exponential bound suffices, or (b) the modern spread/entropy machinery (R-spread set families (ALWZ/Rao's central reduction device), Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao)) when a near-tight bound is needed. Separately, whenever an extremal-family bound is wanted (not existence of a sunflower per se), the Deza–Erdős–Frankl "extract-then-analyze-the-core" method is the reusable move — it decouples "how big can the core be" from "how do disjoint petals interact," letting you import whatever petal-counting tool (Turán, polynomial method, entropy) fits the specific problem.

Related

- Erdős #20 — sunflower conjecture, exponential bound for f(n,k) — the Erdős–Rado sunflower conjecture itself (\$1000 prize for $r=3$): whether $f(k,r)\le C_r^{\,k}$, i.e. whether the classical $k!(r-1)^k$ bound's $k!$ factor can be removed entirely. Still open; this concept page is the definitional/technique substrate underneath it. - R-spread set families (ALWZ/Rao's central reduction device) — the ALWZ/Rao "$R$-spread" reduction device that gives the current best bound $(O(r\log k))^k$ toward Erdős #20 — sunflower conjecture, exponential bound for f(n,k); a direct quantitative descendant of the classical Δ-system extraction argument on this page, replacing repeated pigeonhole with a one-shot probabilistic hitting lemma. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — Rao's coding-theoretic reproof of the spread/sunflower bound, and Tao's Shannon-entropy variant; one of (at least) four independent modern proofs of the key lemma underlying the improved sunflower bounds. - Cap-set problem — max progression-free subset of F_3^n — Naslund–Sawin's polynomial-method (slice-rank) resolution of the *weak*, non-uniform sunflower conjecture (\~$1.89^n$ bound), the clearest fully-solved sibling of the still-open uniform Erdős #20 — sunflower conjecture, exponential bound for f(n,k) question; different technique family (algebraic, not spread/entropy). - Kahn–Kalai expectation-threshold vs. threshold-probability conjecture (Park–Pham theorem) — Frankston–Kahn–Narayanan–Park's fractional expectation-threshold theorem, whose proof reuses the identical spread-family machinery originally built to improve the sunflower bound — evidence the Δ-system/sunflower reduction pattern generalizes well beyond set-family extremal problems into probabilistic thresholds.