On density of subgraphs of halved cubes.

Let S be a family of subsets of a set X of cardinality m and VC-dim (S) be the Vapnik–Chervonenkis dimension of S. Haussler et al. (1994) proved that if G 1 (S) = (V , E) is the subgraph of the hypercube Q m induced by S (called the 1-inclusion graph of S), then | E | | V | ≤ VC-dim (S). Haussler (1995) presented an elegant proof of this inequality using the shifting operation. In this note, we adapt the shifting technique to prove that if S is an arbitrary set family and G 1 , 2 (S) = (V , E) is the 1,2-inclusion graph of S (i.e., the subgraph of the square Q m 2 of the hypercube Q m induced by S), then | E | | V | ≤ d 2 , where d ≔ cVC-dim ∗ (S) is the clique-VC-dimension of 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. [ABSTRACT FROM AUTHOR]