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

Text
2103.10497v2.pdf Download (195kB)  Preview 
Abstract
Given a family F of kelement sets, S1,…,Sr∈F form an {\em rsunflower} 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 rsunflower. We come close to proving this conjecture for families of bounded {\em VapnikChervonenkis dimension}, VCdim(F)≤d. In this case, we show that rsunflowers exist under the slightly stronger assumption F≥210k(dr)2log∗k. Here, log∗ denotes the iterated logarithm function. We also verify the Erd\H osRado conjecture for families F of bounded {\em Littlestone dimension} and for some geometrically defined set systems.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  03 Apr 2023 07:40 
Last Modified:  03 Apr 2023 07:40 
URI:  http://real.mtak.hu/id/eprint/163240 
Actions (login required)
Edit Item 