On density of subgraphs of halved cubes

Victor Chepoi, Arnaud Labourel, Sébastien Ratel

Let $\mathcal{S}$ be a family of subsets of a set $X$ of cardinality $m$ and $\text{VC-dim}(\mathcal{S})$ be the Vapnik-Chervonenkis dimension of $\mathcal{S}$. Haussler, Littlestone,…