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

(→Wikipedia links) |
(→Bibliography: added link to Erdos-Rado) |
||

Line 32: | Line 32: | ||

* Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389 | * Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer, J. Comb. Th. Ser. A 12 (1972), 381–389 | ||

* [https://www.math.uni-bielefeld.de/ahlswede/homepage/public/114.pdf The Complete Nontrivial-Intersection Theorem for Systems of Finite Sets], R. Ahlswede, L. Khachatrian, Journal of Combinatorial Theory, Series A 76, 121-138 (1996). | * [https://www.math.uni-bielefeld.de/ahlswede/homepage/public/114.pdf 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, | + | * [http://renyi.hu/~p_erdos/1960-04.pdf Intersection theorems for systems of sets], P. Erdős, R. Rado, Journal of the London Mathematical Society, Second Series 35 (1960), 85–90. |

* [http://arxiv.org/abs/1205.6847 On the Maximum Number of Edges in a Hypergraph with Given Matching Number], P. Frankl | * [http://arxiv.org/abs/1205.6847 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. | * An intersection theorem for systems of sets, A. V. Kostochka, Random Structures and Algorithms, 9(1996), 213-221. |

## Revision as of 13:42, 4 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(r)^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.

## 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.