The Sunflower Lemma, also known as the delta-system lemma, was proved by Paul Erdos and Richard Rado in 1960. It states that for any positive integers k and r there is a bound f(k, r) such that any family of more than f(k, r) sets, each of size k, must contain a sunflower of r sets, meaning r sets whose pairwise intersections are all identical to a single common kernel. Erdos and Rado showed f(k, r) is at most k! times (r minus 1) to the k, and the lemma is a basic tool in extremal combinatorics and in complexity theory circuit lower bounds, while the question of whether the bound can be improved to an exponential one, the sunflower conjecture, remains open.
Facts
StatementIf k and r are positive integers, then a set system of more than k!(r-1)^k sets, each of cardinality k, contains a sunflower with at least r sets. 1 Classification
Statement Form Connections
Has Statement Form
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Sunflower (mathematics), Wikipedia
Sources
1. Sunflower (mathematics), Wikipedia
Sunflower lemma section
That is, if k and r are positive integers, then a set system W of cardinality greater than k!(r−1)^k of sets of cardinality k contains a sunflower with at least r sets.
Sunflower lemma section, opening sentence
Erdős & Rado (1960, p. 86) proved the sunflower lemma.
- In Branch: Combinatorics, Lead sentence
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.