Improved bounds for the sunflower lemma

A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all. Erdős and Rado proved the sunflower lemma: for any fixed r, any family of sets of size w, with at least about w w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c w for some constant c. In this paper, we improve the bound to about (logw) w . In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is tight up to lower order terms.

• Publication year

  2019

• Venue

  Electron. Colloquium Comput. Complex.

• Publication date

  2019-08-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3357713.3384234arXiv 1908.08483
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Note on Sunflowers

  2020influential reference
• Parameterized Algorithms

  2020cited by this paper
• Decision list compression by mild random restrictions

  2019cited by this paper
• DNF sparsification beyond sunflowers

  2019cited by this paper
• Thresholds versus fractional expectation-thresholds

  2019cited by this paper
• From DNF compression to sunflower theorems via regularity

  2019influential reference
• Coding for Sunflowers

  2019influential reference
• Improved Bound on Sets Including No Sunflower with Three Petals

  2018cited by this paper
• Sunflowers and Quasi-sunflowers from Randomness Extractors

  2018cited by this paper
• Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers

  2018cited by this paper
• Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes

  2017cited by this paper
• White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

  2017cited by this paper
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS

  2016cited by this paper
• Lower bounds for approximation schemes for Closest String

  2015cited by this paper
• The Probabilistic Method

  2015cited by this paper
• Graph Properties in Node-Query Setting: Effect of Breaking Symmetry

  2015cited by this paper
• Sunflowers and Testing Triangle-Freeness of Functions

  2014cited by this paper
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

  2014cited by this paper
• A Bound of the Cardinality of Families Not Containing \(\Delta \) -Systems

  2013cited by this paper
• DNF sparsification and a faster deterministic counting algorithm

  2012cited by this paper
• On sunflowers and matrix multiplication

  2012cited by this paper
• Kernelization of packing problems

  2012cited by this paper
• The Monotone Complexity of k-clique on Random Graphs

  2010influential reference
• Representing (0, 1)-matrices by boolean circuits

  2010cited by this paper
• Data Structuring Problems in the Bit Probe Model

  2007cited by this paper
• Explicit Exclusive Set Systems with Applications to Broadcast Encryption

  2006cited by this paper
• Parameterized Complexity Theory

  2006cited by this paper
• On dynamic range reporting in one dimension

  2005cited by this paper
• On the hardness of approximating minimum vertex cover

  2005cited by this paper
• Parameterized complexity of constraint satisfaction problems

  2004cited by this paper
• The cell probe complexity of succinct data structures

  2003cited by this paper
• Revocation and Tracing Schemes for Stateless Receivers

  2001cited by this paper
• The Permanent Rank of a Matrix

  1999influential reference
• The Probabilistic Method

  1998cited by this paper
• Combinatorial Bounds for Broadcast Encryption

  1998cited by this paper
• Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

  1998cited by this paper
• Bounded Arithmetic and Lower Bounds in Boolean Complexity

  1995influential reference
• Dynamic word problems

  1993cited by this paper
• Linear Circuits over GF(2)

  1990cited by this paper
• A nowhere-zero point in linear mappings

  1989cited by this paper
• Incomparability in parallel computation

  1987cited by this paper
• Computational limitations of small-depth circuits

  1987influential reference
• Every large set of equidistant (0, +1, −1)-vectors forms a sunflower

  1981cited by this paper
• Combinatorial Properties of Systems of Sets

  1978cited by this paper
• Intersection Theorems for Systems of Sets

  1972cited by this paper
• Intersection Theorems for Systems of Sets

  1960influential reference

• Towards odd-sunflowers: Temperate families and lightnings

  2026cites this paper
• The Erdős-Rado sunflower problem for vector spaces

  2026cites this paper
• Erdős-Ko-Rado type results for partitions via spread approximations

  2026influential citation
• Structured sunflowers and Ramsey properties

  2026influential citation
• Frankl's diversity theorem for permutations

  2026cites this paper
• Uniform Set Systems with Uniform Witnesses

  2026influential citation
• Memory Reallocation with Polylogarithmic Overhead

  2026influential citation
• Lifting with Colourful Sunflowers

  2025cites this paper
• A Min-Entropy Approach to Multi-Party Communication Lower Bounds

  2025cites this paper
• Improved Bounds on Rainbow $k$-partite Matchings

  2025cites this paper
• Maxmum Size of a Uniform Family with Bounded VC-dimension

  2025cites this paper
• The story of sunflowers

  2025influential citation
• The Sunflower-Free Process

  2025cites this paper
• Sunflower Bound with a Sub-Logarithmic Base

  2025cites this paper
• Exact results and the structure of extremal families for the Duke--Erd\H{o}s forbidden sunflower problem

  2025cites this paper
• Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies

  2025cites this paper
• The Forbidden Cross Intersection Problem for Permutations

  2025cites this paper
• Forbidding just one intersection for short integer sequences

  2025cites this paper
• A complete $t$-intersection theorem for families of spanning trees

  2025influential citation
• A Bayesian Proof of the Spread Lemma

  2025cites this paper
• The Erd\H{o}s-Rado Sunflower Problem for Vector Spaces

  2025influential citation
• Quasipolynomial Bounds for the Corners Theorem

  2025cites this paper
• Lower Bounds Beyond DNF of Parities

  2025cites this paper
• A note on the maximum diversity of intersecting families in the symmetric group

  2025cites this paper
• Hardness of clique approximation for monotone circuits

  2025influential citation
• Kővári-Sós-Turán theorem for hereditary families

  2025cites this paper
• The Proof Analysis Problem

  2025cites this paper
• Bounded diameter monochromatic component covers

  2025cites this paper
• Rational Exponents for General Graphs

  2025cites this paper
• Maximal sets of a given diameter in Hamming cubes

  2025cites this paper
• Structured Sunflowers

  2025cites this paper
• Sunflowers in Set Systems with Small VC-Dimension

  2024cites this paper
• Searching for (sharp) thresholds in random structures: Where are we now?

  2024cites this paper
• The Frankl-Pach upper bound is not tight for any uniformity

  2024cites this paper
• A Sharp Version of Talagrand’s Selector Process Conjecture and an Application to Rounding Fractional Covers

  2024cites this paper
• Regular subgraphs at every density

  2024cites this paper
• Feasibly Constructive Proof of Schwartz–Zippel Lemma and the Complexity of Finding Hitting Sets

  2024cites this paper
• Adaptive and Oblivious Statistical Adversaries Are Equivalent

  2024cites this paper
• Parks and Recreation: Color Fault-Tolerant Spanners Made Local

  2024influential citation
• Breaking Square-Root Loss Barriers via Min-Entropy

  2024cites this paper
• An almost complete $t$-intersection theorem for permutations

  2024cites this paper
• On small densities defined without pseudorandomness

  2024cites this paper
• One-hundred years of spin

  2023cites this paper
• Sharp thresholds in inference of planted subgraphs

  2023influential citation
• On Rainbow Thresholds

  2023cites this paper
• An improved protocol for ExactlyN with more than 3 players

  2023cites this paper
• Sprinkling with random regular graphs

  2023cites this paper
• Erd\H os-Ko-Rado type results for partitions via spread approximations

  2023cites this paper
• A proof of the Kahn–Kalai conjecture

  2023cites this paper
• Sampling, Flowers and Communication

  2023cites this paper
• Fully Computer-Assisted Proofs in Extremal Combinatorics

  2023cites this paper
• Odd-sunflowers

  2023cites this paper
• Strong Bounds for 3-Progressions

  2023cites this paper
• Sharp thresholds for spanning regular graphs

  2023cites this paper
• On Restricted Intersections and the Sunflower Problem

  2023influential citation
• Sharp hypercontractivity for global functions

  2023cites this paper
• Spanning -cycles in random graphs

  2023cites this paper
• Threshold Phenomena for Random Discrete Structures

  2023cites this paper
• A generalization of diversity for intersecting families

  2023cites this paper
• Sampling and Certifying Symmetric Functions

  2023influential citation
• Top-Down Lower Bounds for Depth-Four Circuits

  2023cites this paper
• On t-intersecting families of permutations

  2023cites this paper
• A Short Proof of Kahn-Kalai Conjecture

  2023cites this paper
• Defective coloring of hypergraphs

  2023cites this paper
• Rigid partitions: From high connectivity to random graphs

  2023cites this paper
• Randomized Algorithms 2022-3

  2022cites this paper
• Lifting with Sunflowers

  2022cites this paper
• Turán numbers of sunflowers

  2022cites this paper
• Sunflowers: from soil to oil

  2022influential citation
• Sunflowers and Robust Sunflowers from Randomness Extractors

  2022cites this paper
• Simulation Methods in Communication Lower Bounds, Revisited

  2022cites this paper
• Upper Bounds For Families Without Weak Delta-Systems

  2022cites this paper
• Spread approximations for forbidden intersections problems

  2022influential citation
• A Proof of the Kahn-Kalai Conjecture

  2022influential citation
• Threshold for Steiner triple systems

  2022cites this paper
• On a conjecture of Talagrand on selector processes and a consequence on positive empirical processes

  2022cites this paper
• Pseudo sunflowers

  2022cites this paper
• Defective Colouring of Hypergraphs

  2022cites this paper
• An Optimal “It Ain’t Over Till It’s Over” Theorem

  2022cites this paper
• Regular subgraphs of linear hypergraphs

  2022cites this paper
• On the Second Kahn-Kalai Conjecture

  2022cites this paper
• Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP

  2022influential citation
• A second moment proof of the spread lemma

  2022cites this paper
• The Park-Pham Theorem with Optimal Convergence Rate

  2022cites this paper
• Rainbow powers of a Hamilton cycle in Gn,p

  2022cites this paper
• Perfect Matchings in Random Sparsifications of Dirac Hypergraphs

  2022cites this paper
• On Disperser/Lifting Properties of the Index and Inner-Product Functions

  2022cites this paper
• Cutting corners

  2022cites this paper
• Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings

  2022cites this paper
• Sharp bounds for rainbow matchings in hypergraphs

  2022cites this paper
• Sunflower Theorems in Monotone Circuit Complexity

  2021cites this paper
• Methods in Extremal Combinatorics

  2021influential citation
• TAME GEOMETRY FOR HODGE THEORY

  2021influential citation
• The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems

  2021cites this paper
• Tur\'{a}n numbers of sunflowers

  2021cites this paper
• On t-Intersecting Hypergraphs with Minimum Positive Codegrees

  2021cites this paper
• Separating Circuits : Switching Lemmas and Random Restrictions

  2021cites this paper
• Sharper bounds on the Fourier concentration of DNFs

  2021cites this paper
• Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random

  2021cites this paper
• The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries

  2021cites this paper