{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:35Z","timestamp":1753893815121,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Fix positive integers $k$ and $d$. We show that, as $n\\to\\infty$, any set system $\\mathcal{A} \\subset 2^{[n]}$ for which the VC dimension of $\\{ \\triangle_{i=1}^k S_i \\mid S_i \\in \\mathcal{A}\\}$ is at most $d$ has size at most $(2^{d\\bmod{k}}+o(1))\\binom{n}{\\lfloor d\/k\\rfloor}$. Here $\\triangle$ denotes the symmetric difference operator. This is a $k$-fold generalisation of a result of Dvir and Moran, and it settles one of their questions.\u00a0\r\nA key insight is that, by a compression method, the problem is equivalent to an extremal set theoretic problem on $k$-wise intersection or union that was originally due to Erd\u0151s and Frankl.\r\nWe also give an example of a family $\\mathcal{A} \\subset 2^{[n]}$ such that the VC dimension of $\\mathcal{A}\\cap \\mathcal{A}$ and of $\\mathcal{A}\\cup \\mathcal{A}$ are both at most $d$, while $\\lvert \\mathcal{A} \\rvert = \\Omega(n^d)$. This provides a negative answer to another question of Dvir and Moran.<\/jats:p>","DOI":"10.37236\/8288","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T07:04:52Z","timestamp":1578639892000},"source":"Crossref","is-referenced-by-count":1,"title":["VC Dimension and a Union Theorem for Set Systems"],"prefix":"10.37236","volume":"26","author":[{"given":"Stijn","family":"Cambie","sequence":"first","affiliation":[]},{"given":"Ant\u00f3nio","family":"Gir\u00e3o","sequence":"additional","affiliation":[]},{"given":"Ross J.","family":"Kang","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2019,8,2]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i3p24\/7884","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i3p24\/7884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T04:11:00Z","timestamp":1579234260000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v26i3p24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,2]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,7,4]]}},"URL":"https:\/\/doi.org\/10.37236\/8288","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2019,8,2]]},"article-number":"P3.24"}}