Sunflowers in Set Systems of Bounded Dimension

Given a family F of k-element sets, S-1,..., S-r is an element of F form an r -sunflower if S-i boolean AND Sj = S-i ' boolean AND S-j ' for all i not equal j and i 'not equal j '. According to a famous conjecture of Erd os and Rado (JAMA35: 85-90, 1960), there is a constant c = c(r) such that if |F| >= c(k), then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) <= d. In this case, we showthat r-sunflowers exist under the slightly stronger assumption |F| >= 2(10k(dr)2 log* k). Here, log* denotes the iterated logarithm function. We also verify the Erdos-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.

Automated summary

According to the famous conjecture of Erdos and Rado, for families F with bounded VC-dimension, if |F| >= 2(10k(dr)2 log* k), then F contains an r-sunflower.