(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## The problem

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

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

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

$\displaystyle f(k,r) \leq D(r,\alpha) k! \left( \frac{(\log\log\log k)^2}{\alpha \log\log k} \right)^k$

for any $\alpha \lt 1$, and some $D(r,\alpha)$ depending on $r,\alpha$, proven by Kostkocha from 1996. The objective of this project is to improve this bound, ideally to obtain the Erdos-Rado conjecture

$\displaystyle f(k,r) \leq C^k$

for some $C=C(r)$ depending on $r$ only. This is known for $r=1,2$(indeed we have $f(k,r)=1$ in those cases) but remains open for larger r.

## Variants and notation

Given a family $\cal F$ of sets and a set S, the star of S is the subfamily of those sets in $\cal F$ containing S, and the link of S is obtained from the star of S by deleting the elements of S from every set in the star. (We use the terms link and star because we do want to consider eventually hypergraphs as geometric/topological objects.)

We can restate the delta system problem as follows: f(k,r) is the maximum size of a family of k-sets such that the link of every set A does not contain r pairwise disjoint sets.

Let f(k,r;m,n) denote the largest cardinality of a family of k-sets from {1,2,…,n} such that that the link of every set A of size at most m-1 does not contain r pairwise disjoint sets. Thus f(k,r) = f(k,r;k,n) for n large enough.

Conjecture 1: $f(k,r;m,n) \leq C_r^k n^{k-m}$ for some $C_r$ depending only on r.

This conjecture implies the Erdos-Ko-Rado conjecture (set m=k). The Erdos-Ko-Rado theorem asserts that

$f(k,2;1,n) = \binom{n-1}{k-1}$ (1)

when $n \geq 2k$, which is consistent with Conjecture 1. More generally, Erdos, Ko, and Rado showed

$f(k,2;m,n) = \binom{n-m}{k-m}$

when $n$ is sufficiently large depending on k,m. The case of smaller n was treated by several authors culminating in the work of Ahlswede and Khachatrian.

Erdos conjectured that

$f(k,r;1,n) = \max( \binom{rk-1}{k}, \binom{n}{k} - \binom{n-r}{k} )$

for $n \geq rk$, generalising (1), and again consistent with Conjecture 1. This was established for k=2 by Erdos and Gallai, and for r=3 by Frankl (building on work by Luczak-Mieczkowska).

A family of k-sets is balanced (or k-colored) if it is possible to color the elements with k colors so that every set in the family is colorful.

Reduction (folklore): It is enough to prove Erdos-Rado Delta-system conjecture for the balanced case.

Proof: Divide the elements into d color classes at random and take only colorful sets. The expected size of the surviving colorful sets is $k!/k^k \cdot |\cal F|$.

Hyperoptimistic conjecture: The maximum size of a balanced collection of k-sets without a sunflower of size r is (r-1)^k.

Disproven for $k=3,r=3$: set $|V_1|=|V_2|=|V_3|=3$ and use ijk to denote the 3-set consisting of the i^th element of V_1, j^th element of V_2, and k^th element of V_3. Then 000, 001, 010, 011, 100, 101, 112, 122, 212 is a balanced family of 9 3-sets without a 3-sunflower.

A weak sunflower (weak Delta-system) of size $r$ is a family of $r$ sets, $A_1,\ldots,A_r$, such that their pairwise intersections have the same size, i.e., $|A_i\cap A_j|=|A_{i'}\cap A_{j'}|$ for every $i\ne j$ and $i'\ne j'$. If we denote the size of the largest family of $k$-sets without an $r$-weak sunflower by $g(k,r)$, by definition we have $g(k,r)\le f(k,r)$. For this function we also know that $g(a+b,r)\ge g(a,r)g(b,r)$, as shown by Abbott-Hanson in On finite Δ-systems II.

Also, if we denote by $R_r(k)-1$ the size of the largest complete graph whose edges can be colored with $r$ colors such that there is no monochromatic clique on $k$ vertices, then we have $g(k,r)\le R_r(k)-1$, as we can color the edges running between the $k$-sets of our weak sunflower-free family with the intersection sizes. For all three functions only exponential lower bounds and factorial type upper bounds are known.

Denote by $3DES(n)$ the largest integer such that there is a group of size $n$ and a subset $S$ of size $3DES(n)$ without three disjoint equivoluminous subsets, i.e., there is no $S=S_1\cup^* S_2\cup^* S_3\cup^* S_{rest}$ such that $\sum_{s\in S_1} s=\sum_{s\in S_2} s=\sum_{s\in S_3} s$. As noticed by Alon-Shpilka-Umans, ${3DES(n) \choose DES(n)} / n \le g(DES(n),3)$ holds, thus if $g(k,3)$ grows exponentially, then $3DES(n)=O(\log n)$.

## Small values

Below is a collection of known constructions for small values, taken from Abbott-Exoo. Boldface stands for matching upper bound (and best known upper bounds are planned to be added to other entries). Also note that for $k$ fixed we have $f(k,r)=k^r+o(k^r)$ from Kostochka-Rödl-Talysheva.

r\k 2 3 4 5 6 ...k
3 6 20 54- 160- 600- ~3.16^k
4 10 38- 114- 380- 1444- ~3.36^k
5 20 88- 400- 1760- 8000- ~4.24^k
6 27 146- 730- 3942- 21316- ~5.26^k