Exponential sunflower bound for bounded VC-dimension
Conjecture 1.1 · arXiv:2103.10497
Status partial high confidence
The conjecture that $f^d_r(k) \leq C^k$ for all $d \geq 1$ and $r \geq 3$ is proven for $d=1$ by the original paper (Theorem 1.2). For $d \geq 2$, Balogh, Bernshteyn, Delcourt, Ferber, and Pham (arXiv:2408.04165, 2024) substantially improved the bound from $2^{10k(dr)^2 \log^* k}$ to $(Cr(\log d + \log^* k))^k$, but the pure exponential $C^k$ with $C = C(d,r)$ independent of $k$ remains open for $d \geq 2$. The $d=1$ case is also resolved sharply in 2408.04165 with the tight bound $(r-1)^k$.
Cited literature (1)
-
Proves that any family of $\ell$-element sets with VC-dimension at most $d$ and size exceeding $(Cr(\log d + \log^* \ell))^\ell$ contains an $r$-sunflower, improving Fox–Pach–Suk's bound; also obtains the sharp bound $(r-1)^k$ for $d=1$, but the conjecture for $d \geq 2$ (pure exponential $C^k$) remains open.
Reviewer notes. The paper arXiv:2408.04165 (published in Combinatorica 2025) is the main follow-up; it removes the double-exponential dependence on $\log^* k$ from the exponent but the base still contains a $\log^* k$ factor, so the conjecture for $d \geq 2$ is not yet resolved. No other post-2021 paper resolving the full conjecture was found.
Context
The authors note that the Erdős-Rado sunflower conjecture implies this weaker statement about families of bounded VC-dimension $d$, where $f^d_r(k)$ is the minimum family size guaranteeing an $r$-sunflower among $k$-sets with VC-dimension at most $d$. The paper proves the conjecture for $d = 1$ (Theorem 1.2) and establishes the slightly weaker bound $f^d_r(k) \leq 2^{10k(dr)^2 \log^* k}$ for $d \geq 2$ (Theorem 1.3), leaving the full conjecture open for $d \geq 2$.
Notes. PDF source. Conjecture is explicitly labelled in the paper. The case $d=1$ is resolved by Theorem 1.2; the case $d \geq 2$ remains open.
Source paper
Sunflowers in set systems of bounded dimension
Jacob Fox, Janos Pach, Andrew Suk · 2021-03-25
https://arxiv.org/abs/2103.10497
PDF source