{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:40:07Z","timestamp":1748857207993,"version":"3.41.0"},"reference-count":7,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T00:00:00Z","timestamp":1746576000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T00:00:00Z","timestamp":1746576000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Schaerf fund of the Einstein Institute of Mathematics, Hebrew University of Jerusalem"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1832\/19"],"award-info":[{"award-number":["1832\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Given natural numbers <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$k\\le s\\le n$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>s<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, we ask: what is the minimal VC-dimension of a family <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\mathcal {F}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>F<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> of <jats:italic>s<\/jats:italic>-subsets of [<jats:italic>n<\/jats:italic>] that covers all <jats:italic>k<\/jats:italic>-subsets of [<jats:italic>n<\/jats:italic>]? We first show that for sufficiently large <jats:italic>n<\/jats:italic> this number is always <jats:italic>k<\/jats:italic>, and construct families which give a lower bound for the actual growth of this stabilization point.<\/jats:p>","DOI":"10.1007\/s00373-025-02922-9","type":"journal-article","created":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T14:11:57Z","timestamp":1746627117000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Set Systems with Covering Properties and Low VC-Dimension"],"prefix":"10.1007","volume":"41","author":[{"given":"George","family":"Peterzil","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0123-9545","authenticated-orcid":false,"given":"Johanna","family":"Steinmeyer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,7]]},"reference":[{"key":"2922_CR1","doi-asserted-by":"publisher","unstructured":"Alon, N., Moran, S., Yehudayoff, A.: Sign rank versus VC dimension. In: Annual Conference Computational Learning Theory (2015). https:\/\/doi.org\/10.1070\/SM8780","DOI":"10.1070\/SM8780"},{"key":"2922_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/S1474748023000464","author":"M Bays","year":"2023","unstructured":"Bays, M., Ben-Neria, O., Kaplan, I., Simon, P.: On large definable subsets in NIP. J. Inst. Math. Jussieu (2023). https:\/\/doi.org\/10.1017\/S1474748023000464","journal-title":"J. Inst. Math. Jussieu"},{"key":"2922_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2022.103528","author":"N Frankl","year":"2022","unstructured":"Frankl, N., Kiselev, S., Kupavskii, A., Patk\u00f3s, B.: VC-saturated set systems. Eur. J. Combin. (2022). https:\/\/doi.org\/10.1016\/j.ejc.2022.103528","journal-title":"Eur. J. Combin."},{"key":"2922_CR4","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Combin. Theory 13, 145\u2013147 (1972). https:\/\/doi.org\/10.1016\/0097-3165(72)90019-2","journal-title":"J. Combin. Theory"},{"key":"2922_CR5","doi-asserted-by":"publisher","first-page":"247","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S Shelah","year":"1972","unstructured":"Shelah, S.: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41, 247\u2013261 (1972). https:\/\/doi.org\/10.2140\/pjm.1972.41.247","journal-title":"Pac. J. Math."},{"key":"2922_CR6","doi-asserted-by":"publisher","unstructured":"Simon, P.: A Guide to NIP Theories. Lecture Notes in Logic. Cambridge University Press (2015). https:\/\/doi.org\/10.1017\/CBO9781107415133","DOI":"10.1017\/CBO9781107415133"},{"issue":"2","key":"2922_CR7","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264\u2013280 (1971). https:\/\/doi.org\/10.1137\/1116025","journal-title":"Theory Probab. Appl."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02922-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02922-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02922-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T09:15:44Z","timestamp":1748855744000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02922-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,7]]},"references-count":7,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["2922"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02922-9","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,5,7]]},"assertion":[{"value":"9 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"68"}}