Set Systems with Covering Properties and Low VC-Dimension

Abstract Given natural numbers $$k\le s\le n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>s</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , we ask: what is the minimal VC-dimension of a family $$\mathcal {F}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>F</mml:mi> </mml:math> 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.