Sunflowers in Set Systems with Small VC-Dimension

Abstract A family of r distinct sets $$\{A_1,\ldots , A_r\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:msub> <mml:mi>A</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>A</mml:mi> <mml:mi>r</mml:mi> </mml:msub> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> is an r -sunflower if for all $$1 \leqslant i &lt; j\leqslant r$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>⩽</mml:mo> <mml:mi>i</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>j</mml:mi> <mml:mo>⩽</mml:mo> <mml:mi>r</mml:mi> </mml:mrow> </mml:math> and $$1 \leqslant i' &lt; j'\leqslant r$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>⩽</mml:mo> <mml:msup> <mml:mi>i</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>&lt;</mml:mo> <mml:msup> <mml:mi>j</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>⩽</mml:mo> <mml:mi>r</mml:mi> </mml:mrow> </mml:math> , we have $$A_i\cap A_j = A_{i'}\cap A_{j'}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>A</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:mo>∩</mml:mo> <mml:msub> <mml:mi>A</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>A</mml:mi> <mml:msup> <mml:mi>i</mml:mi> <mml:mo>′</mml:mo> </mml:msup> </mml:msub> <mml:mo>∩</mml:mo> <mml:msub> <mml:mi>A</mml:mi> <mml:msup> <mml:mi>j</mml:mi> <mml:mo>′</mml:mo> </mml:msup> </mml:msub> </mml:mrow> </mml:math> . Erdős and Rado conjectured in 1960 that every family $$\mathcal {H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> of $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> -element sets of size at least $$K(r)^\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>r</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>ℓ</mml:mi> </mml:msup> </mml:mrow> </mml:math> contains an r -sunflower, where K ( r ) is some function that depends only on r . We prove that if $$\mathcal {H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> is a family of $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> -element sets of VC-dimension at most d and $$|\mathcal H| &gt; (C r(\log d+\log ^*\ell ))^\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>H</mml:mi> <mml:mo>|</mml:mo> <mml:mo>&gt;</mml:mo> </mml:mrow> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>C</mml:mi> <mml:mi>r</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:msup> <mml:mo>log</mml:mo> <mml:mo>∗</mml:mo> </mml:msup> <mml:mi>ℓ</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>ℓ</mml:mi> </mml:msup> </mml:mrow> </mml:math> for some absolute constant $$C &gt; 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML">