On density of subgraphs of halved cubes

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$\mathrm{.}Haussler,Littlestone,andWarmuth(Inf\mathrm{.}Comput\mathrm{.},1994)provedthatif$G_1(\mathcal S)=(V,E)$isthesubgraphofthehypercube$Q_m$inducedby$\mathcal S$(calledthe1-inclusiongraphof$\mathcal S$),then$\frac{|E|}{|V|}\le $\text{VC-dim}$({\mathcal S})$. Haussler (J. Combin. Th. A, 1995) presented an elegant proof of this inequality using the shifting operation. In this note, we adapt the shifting technique to prove that if $\mathcal{S}$ is an arbitrary set family and $G_{1,2}(\mathcal{S})=(V,E)$ is the 1,2-inclusion graph of $\mathcal{S}$ (i.e., the subgraph of the square $Q_m^2$ of the hypercube $Q_m$ induced by $\mathcal{S}$), then $\frac{|E|}{|V|}\le \binom{d}{2}$,where$d:=$\text{cVC-dim}$^*(\mathcal S)$ is the clique-VC-dimension of $\mathcal{S}$ (which we introduce in this paper). The 1,2-inclusion graphs are exactly the subgraphs of halved cubes and comprise subgraphs of Johnson graphs as a subclass.