<p>A family of <i>r</i> distinct sets <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\{A_1,\ldots , A_r\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <msub> <mi>A</mi> <mn>1</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>A</mi> <mi>r</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> is an <i>r</i>-sunflower if for all <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(1 \leqslant i &lt; j\leqslant r\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>⩽</mo> <mi>i</mi> <mo>&lt;</mo> <mi>j</mi> <mo>⩽</mo> <mi>r</mi> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(1 \leqslant i' &lt; j'\leqslant r\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1</mn> <mo>⩽</mo> <msup> <mi>i</mi> <mo>′</mo> </msup> <mo>&lt;</mo> <msup> <mi>j</mi> <mo>′</mo> </msup> <mo>⩽</mo> <mi>r</mi> </mrow> </math></EquationSource> </InlineEquation>, we have <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(A_i\cap A_j = A_{i'}\cap A_{j'}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mi>i</mi> </msub> <mo>∩</mo> <msub> <mi>A</mi> <mi>j</mi> </msub> <mo>=</mo> <msub> <mi>A</mi> <msup> <mi>i</mi> <mo>′</mo> </msup> </msub> <mo>∩</mo> <msub> <mi>A</mi> <msup> <mi>j</mi> <mo>′</mo> </msup> </msub> </mrow> </math></EquationSource> </InlineEquation>. Erdős and Rado conjectured in 1960 that every family <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\mathcal {H}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-element sets of size at least <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(K(r)^\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>K</mi> <msup> <mrow> <mo stretchy="false">(</mo> <mi>r</mi> <mo stretchy="false">)</mo> </mrow> <mi>ℓ</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> contains an <i>r</i>-sunflower, where <i>K</i>(<i>r</i>) is some function that depends only on <i>r</i>. We prove that if <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mathcal {H}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> is a family of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-element sets of VC-dimension at most <i>d</i> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(|\mathcal H| &gt; (C r(\log d+\log ^*\ell ))^\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mi mathvariant="script">H</mi> <mo stretchy="false">|</mo> <mo>&gt;</mo> </mrow> <msup> <mrow> <mo stretchy="false">(</mo> <mi>C</mi> <mi>r</mi> <mrow> <mo stretchy="false">(</mo> <mo>log</mo> <mi>d</mi> <mo>+</mo> <msup> <mo>log</mo> <mo>∗</mo> </msup> <mi>ℓ</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mi>ℓ</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> for some absolute constant <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(C &gt; 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>C</mi> <mo>&gt;</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\mathcal {H}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation> contains an <i>r</i>-sunflower. This improves a recent result of Fox, Pach, and Suk. When <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(d=1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, we obtain a sharp bound, namely that <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(|\mathcal H| &gt; (r-1)^\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mrow> <mo stretchy="false">|</mo> <mi mathvariant="script">H</mi> <mo stretchy="false">|</mo> <mo>&gt;</mo> <mrow> <mo stretchy="false">(</mo> <mi>r</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </mrow> <mi>ℓ</mi> </msup> </math></EquationSource> </InlineEquation> is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Sunflowers in Set Systems with Small VC-Dimension

  • József Balogh,
  • Anton Bernshteyn,
  • Michelle Delcourt,
  • Asaf Ferber,
  • Huy Tuan Pham

摘要

A family of r distinct sets \(\{A_1,\ldots , A_r\}\) { A 1 , , A r } is an r-sunflower if for all \(1 \leqslant i < j\leqslant r\) 1 i < j r and \(1 \leqslant i' < j'\leqslant r\) 1 i < j r , we have \(A_i\cap A_j = A_{i'}\cap A_{j'}\) A i A j = A i A j . Erdős and Rado conjectured in 1960 that every family \(\mathcal {H}\) H of \(\ell \) -element sets of size at least \(K(r)^\ell \) K ( r ) contains an r-sunflower, where K(r) is some function that depends only on r. We prove that if \(\mathcal {H}\) H is a family of \(\ell \) -element sets of VC-dimension at most d and \(|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell \) | H | > ( C r ( log d + log ) ) for some absolute constant \(C > 0\) C > 0 , then \(\mathcal {H}\) H contains an r-sunflower. This improves a recent result of Fox, Pach, and Suk. When \(d=1\) d = 1 , we obtain a sharp bound, namely that \(|\mathcal H| > (r-1)^\ell \) | H | > ( r - 1 ) is sufficient. Along the way, we establish a strengthening of the Kahn–Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.