Sunflowers in set systems of bounded dimension

Fox, Jacob and Pach, János and Suk, Andrew (2023) Sunflowers in set systems of bounded dimension. COMBINATORICA. ISSN 0209-9683

Preview

Text 2103.10497v2.pdf Download (195kB) | Preview

Abstract

Given a family F of k-element sets, S1,…,Sr∈F form an {\em r-sunflower} if Si∩Sj=Si′∩Sj′ for all i≠j and i′≠j′. According to a famous conjecture of Erd\H os and Rado (1960), there is a constant c=c(r) such that if |F|≥ck, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded {\em Vapnik-Chervonenkis dimension}, VC-dim(F)≤d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F|≥210k(dr)2log∗k. Here, log∗ denotes the iterated logarithm function. We also verify the Erd\H os-Rado conjecture for families F of bounded {\em Littlestone dimension} and for some geometrically defined set systems.

Actions (login required)

Edit Item