Back to Search
Start Over
On density of subgraphs of halved cubes.
- Source :
-
European Journal of Combinatorics . Aug2019, Vol. 80, p57-70. 14p. - Publication Year :
- 2019
-
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]
- Subjects :
- *CUBES
*SUBGRAPHS
*HYPERCUBES
*DENSITY
*EVIDENCE
*MATHEMATICAL equivalence
Subjects
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 80
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 137051999
- Full Text :
- https://doi.org/10.1016/j.ejc.2018.02.039