Difference between revisions of "The Erdos-Rado sunflower lemma"

From Polymath1Wiki
Jump to: navigation, search
(Bibliography: added link to Erdos-Rado)
(The problem)
Line 13: Line 13:
 
for any <math>\alpha < 1</math>, and some <math>D(r,\alpha)</math> depending on <math>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
 
for any <math>\alpha < 1</math>, and some <math>D(r,\alpha)</math> depending on <math>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 f(k,r) \leq C(r)^k </math>
+
:<math>\displaystyle f(k,r) \leq C^k </math>
  
for some <math>C(r)</math> depending on <math>k</math>.  This is known for <math>r=1,2</math> but remains open for larger r.
+
for some <math>C=C(r)</math> depending on <math>r</math> only.  This is known for <math>r=1,2</math> but remains open for larger r.
  
 
== Threads ==
 
== Threads ==

Revision as of 08:52, 6 November 2015

The problem

A sunflower (a.k.a. Delta-system) of size [math]r[/math] is a family of sets [math]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]f(k,r)[/math] so that every family [math]\cal F[/math] of [math]k[/math]-sets with more than [math]f(k,r)[/math] members contains a sunflower of size [math]r[/math].

(We denote by [math]f(k,r)[/math] the smallest integer that suffices for the assertion of the theorem to be true.) The simple proof giving [math]f(k,r)\le k! (r-1)^k[/math] can be found here.

The best known general upper bound on [math]f(k,r)[/math] (in the regime where [math]r[/math] is bounded and [math]k[/math] is large) is

[math]\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]\alpha \lt 1[/math], and some [math]D(r,\alpha)[/math] depending on [math]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 f(k,r) \leq C^k [/math]

for some [math]C=C(r)[/math] depending on [math]r[/math] only. This is known for [math]r=1,2[/math] but remains open for larger r.

Threads

External links

Bibliography

Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!