Coding for Sunflowers

DOI10.19086/DA.11887MaRDI QIDQ5126764zbMATH OpenOpenAlexFDO

Authors

Publication date 20 October 2020

Published in discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.04774

zbMATH Keywords

combinatoricssunflower

Mathematics Subject Classification ID

Extremal set theory (05D05) Coding theorems (Shannon theory) (94A24)

Abstract: A sunflower is a family of sets that have the same pairwise intersections. We simplify a recent result of Alweiss, Lovett, Wu and Zhang that gives an upper bound on the size of every family of sets of size $k$ that does not contain a sunflower. We show how to use the converse of Shannon's noiseless coding theorem to give a cleaner proof of their result.

Recommendations

• Improved bounds for the sunflower lemma
• Multicolour sunflowers
• Note on sunflowers
• Sunflowers: from soil to oil
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS

Cites work

• Are many small sets explicitly small?
• Arithmetic progressions in subset sums
• DNF sparsification and a faster deterministic counting algorithm
• DNF sparsification beyond sunflowers
• Dynamic word problems
• scientific article; zbMATH DE number 7250167 (Why is no real title available?)
• Intersection Theorems for Systems of Sets
• The cell probe complexity of succinct data structures
• The monotone complexity of \(k\)-clique on random graphs
• Thresholds versus fractional expectation-thresholds

Cited in

(25)

• An improved upper bound for the size of a sunflower-free family
• Thresholds versus fractional expectation-thresholds
• Unavoidable hypergraphs
• Note on sunflowers
• Improved bounds for the sunflower lemma
• On the hat guessing number of graphs
• On the size of shadow-added intersecting families
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Sunflowers and quasi-sunflowers from randomness extractors
• Sunflowers: from soil to oil
• Turán numbers of sunflowers
• Monotone circuit lower bounds from robust sunflowers
• THE IONESCU–WAINGER MULTIPLIER THEOREM AND THE ADELES
• On restricted intersections and the sunflower problem
• The Park-Pham theorem with optimal convergence rate
• Defective coloring of hypergraphs
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Towards odd-sunflowers: temperate families and lightnings
• The story of sunflowers
• New bounds on families without large sunflowers
• Sharp thresholds in inference of planted subgraphs
• Sunflowers in set systems of bounded dimension
• Approximate sunflowers with convex sets
• Focal-free uniform hypergraphs and codes
• Linear dependencies, polynomial factors in the Duke-Erdős forbidden sunflower problem

This page was built for publication: Coding for Sunflowers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5126764)