2026-08-11T03:23:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13836 2024-03-06T10:52:50Z ddc:004 open_access

Sunflowers in Set Systems of Bounded Dimension Fox, Jacob Pach, János Suk, Andrew Sunflower VC-dimension Littlestone dimension pseudodisks Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (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 show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacob Fox and János Pach and Andrew Suk 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.37 urn:nbn:de:0030-drops-138366 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.37 eng https://creativecommons.org/licenses/by/4.0/legalcode