UPPER BOUNDS FOR SUNFLOWER-FREE SETS

Abstract: A collection of

k

sets is said to form a

k

-sunflower, or

D e l t a

-system, if the intersection of any two sets from the collection is the same, and we call a family of sets

m a t h c a l F

sunflower-free if it contains no sunflowers. Following the recent breakthrough of Ellenberg and Gijswijt and Croot, Lev and Pach we apply the polynomial method directly to ErdH{o}s-Szemer'{e}di sunflower problem and prove that any sunflower-free family

m a t h c a l F

of subsets of

1, 2, d o t s, n

has size at most [ |mathcal{F}|leq3nsum_{kleq n/3}�inom{n}{k}leqleft(frac{3}{2^{2/3}} ight)^{n(1+o(1))}. ] We say that a set

A s u b s e t (m a t h b b Z / D m a t h b b Z)^{n} = {1, 2, d o t s, D}^{n}

for

D > 2

is sunflower-free if every distinct triple

x, y, z i n A

there exists a coordinate

i

where exactly two of

x_{i}, y_{i}, z_{i}

are equal. Using a version of the polynomial method with characters

c h i : m a t h b b Z / D m a t h b b Z i g h t a r r o w m a t h b b C

instead of polynomials, we show that any sunflower-free set

A s u b s e t (m a t h b b Z / D m a t h b b Z)^{n}

has size [ |A|leq c_{D}^{n} ] where

c_{D} = f r a c 3 2^{2 / 3} (D - 1)^{2 / 3}

. This can be seen as making further progress on a possible approach to proving the ErdH{o}s-Rado sunflower conjecture, which by the work of Alon, Sphilka and Umans is equivalent to proving that

c_{D} l e q C

for some constant

C

independent of

D

.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: UPPER BOUNDS FOR SUNFLOWER-FREE SETS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280253)