Scholarlink

<p>Given natural numbers <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2922_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\le s\le n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≤</mo> <mi>s</mi> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, we ask: what is the minimal VC-dimension of a family <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2922_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="17" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {F}\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> of <i>s</i>-subsets of [<i>n</i>] that covers all <i>k</i>-subsets of [<i>n</i>]? We first show that for sufficiently large <i>n</i> this number is always <i>k</i>, and construct families which give a lower bound for the actual growth of this stabilization point.</p>

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

Set Systems with Covering Properties and Low VC-Dimension

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年5月7日

查看全文
  • George Peterzil,
  • Johanna Steinmeyer

摘要

Given natural numbers \(k\le s\le n\) k ≤ s ≤ n , we ask: what is the minimal VC-dimension of a family \(\mathcal {F}\) F of s-subsets of [n] that covers all k-subsets of [n]? We first show that for sufficiently large n this number is always k, and construct families which give a lower bound for the actual growth of this stabilization point.