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

(→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 | + | :<math>\displaystyle f(k,r) \leq C^k </math> |

− | for some <math>C(r)</math> depending on <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 == | == Threads == |

## Revision as of 07: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

- 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]\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.