2017/11/30 by Victor Chepoi, Chepoi, Victor, Arnaud Labourel +3
Computer Science · Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1711.11414
openalex publication_date 2017/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \mathcal S be a family of subsets of a set X of cardinality m and VC-dim(\mathcal S) be the Vapnik-Chervonenkis dimension of \mathcal S. Haussler, Littlestone, and Warmuth (Inf. Comput., 1994) proved that if G1(\mathcal S)=(V,E) is the subgraph of the hypercube Qm induced by \mathcal S (called the 1-inclusion graph of \mathcal S), then (|E|)/(|V|)≤ 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 G1,2(\mathcal S)=(V,E) is the 1,2-inclusion graph of \mathcal S (i.e., the subgraph of the square Q2m of the hypercube Qm induced by \mathcal S), then (|E|)/(|V|)≤ \binomd2, where d:=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.