1. On density of subgraphs of halved cubes.
- Author
-
Chepoi, Victor, Labourel, Arnaud, and Ratel, Sébastien
- Subjects
- *
CUBES , *SUBGRAPHS , *HYPERCUBES , *DENSITY , *EVIDENCE , *MATHEMATICAL equivalence - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF