The Erdos-Rado sunflower lemma
The problem
A sunflower (a.k.a. Delta-system) of size [math]\displaystyle{ r }[/math] is a family of sets [math]\displaystyle{ A_1, A_2, \dots, A_r }[/math] such that every element that belongs to more than one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that
- Erdos-Rado Delta-system theorem: There is a function [math]\displaystyle{ f(k,r) }[/math] so that every family [math]\displaystyle{ \cal F }[/math] of [math]\displaystyle{ k }[/math]-sets with more than [math]\displaystyle{ f(k,r) }[/math] members contains a sunflower of size [math]\displaystyle{ r }[/math].
(We denote by [math]\displaystyle{ f(k,r) }[/math] the smallest integer that suffices for the assertion of the theorem to be true.) The simple proof giving [math]\displaystyle{ f(k,r)\le k! (r-1)^k }[/math] can be found here.
The best known general upper bound on [math]\displaystyle{ f(k,r) }[/math] (in the regime where [math]\displaystyle{ r }[/math] is bounded and [math]\displaystyle{ k }[/math] is large) is
- [math]\displaystyle{ \displaystyle f(k,r) \leq D(r,\alpha) k! \left( \frac{(\log\log\log k)^2}{\alpha \log\log k} \right)^k }[/math]
for any [math]\displaystyle{ \alpha \lt 1 }[/math], and some [math]\displaystyle{ D(r,\alpha) }[/math] depending on [math]\displaystyle{ r,\alpha }[/math], proven by Kostkocha from 1996. The objective of this project is to improve this bound, ideally to obtain the Erdos-Rado conjecture
- [math]\displaystyle{ \displaystyle f(k,r) \leq C(r)^k }[/math]
for some [math]\displaystyle{ C(r) }[/math] depending on [math]\displaystyle{ k }[/math]. This is known for [math]\displaystyle{ r=1,2 }[/math] but remains open for larger r.
Threads
- Polymath10: The Erdos Rado Delta System Conjecture, Gil Kalai, Nov 2, 2015. Active
External links
- Sunflower (mathematics) (Wikipedia article)
- What is the best lower bound for 3-sunflowers? (Mathoverflow)
Bibliography
Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!
- Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389
- The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets, R. Ahlswede, L. Khachatrian, Journal of Combinatorial Theory, Series A 76, 121-138 (1996).
- Intersection theorems for systems of sets, P. Erdős, R. Rado, Journal of the London Mathematical Society, Second Series 35 (1960), 85–90.
- On the Maximum Number of Edges in a Hypergraph with Given Matching Number, P. Frankl
- An intersection theorem for systems of sets, A. V. Kostochka, Random Structures and Algorithms, 9(1996), 213-221.
- Extremal problems on [math]\displaystyle{ \Delta }[/math]-systems, A. V. Kostochka
- On Erdos' extremal problem on matchings in hypergraphs, T. Luczak, K. Mieczkowska
- Intersection theorems for systems of sets, J. H. Spencer, Canad. Math. Bull. 20 (1977), 249-254.
