REAL

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

[img]
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.

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 Edit Item