Two-dimensional partial cubes
From MaRDI portal
Abstract: We investigate the structure of two-dimensional partial cubes, i.e., of isometric subgraphs of hypercubes whose vertex set defines a set family of VC-dimension at most 2. Equivalently, those are the partial cubes which are not contractible to the 3-cube (here contraction means contracting the edges corresponding to the same coordinate of the hypercube). We show that our graphs can be obtained from two types of combinatorial cells (gated cycles and gated full subdivisions of complete graphs) via amalgams. The cell structure of two-dimensional partial cubes enables us to establish a variety of results. In particular, we prove that all partial cubes of VC-dimension 2 can be extended to ample aka lopsided partial cubes of VC-dimension 2, yielding that the set families defined by such graphs satisfy the sample compression conjecture by Littlestone and Warmuth (1986). Furthermore we point out relations to tope graphs of COMs of low rank and region graphs of pseudoline arrangements.
Recommendations
Cites work
- scientific article; zbMATH DE number 53152 (Why is no real title available?)
- scientific article; zbMATH DE number 1221771 (Why is no real title available?)
- scientific article; zbMATH DE number 1113985 (Why is no real title available?)
- scientific article; zbMATH DE number 2053394 (Why is no real title available?)
- scientific article; zbMATH DE number 863503 (Why is no real title available?)
- A combinatorial problem; stability and order for models and theories in infinitary languages
- Basic phylogenetic combinatorics.
- Bounding embeddings of VC classes into maximum classes
- COMs: complexes of oriented matroids
- Cellular bipartite graphs
- Combinatorics of lopsided sets
- Convex excess in partial cubes
- Convexity in partial cubes: the hull number
- Defect Sauer results
- Distance-preserving subgraphs of hypercubes
- Gated sets in metric spaces
- Geometry of cuts and metrics
- Graphs and cubes
- Graphs of some CAT(0) complexes
- Handbook of product graphs
- Hypercellular graphs: partial cubes without \(Q_3^-\) as partial cube minor
- Isometric subgraphs of Hamming graphs and d-convexity
- Labeled compression schemes for extremal classes
- Lopsided sets and orthant-intersection by convex sets
- Metric graph theory and geometry: a survey
- Netlike partial cubes. I. General properties
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- On the density of families of sets
- On tope graphs of complexes of oriented matroids
- Orientability of matroids
- Oriented matroids
- Poset topology and homological invariants of algebras arising in algebraic combinatorics
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Recognizing partial cubes in quadratic time
- Sample Compression Schemes for VC Classes
- Separation of two convex sets in convexity structures
- Shattering news
- Shattering-extremal set systems of VC dimension at most 2
- Sphere packing numbers for subsets of the Boolean \(n\)-cube with bounded Vapnik-Chervonenkis dimension
- The Varchenko determinant for oriented matroids
- The axiomatization of affine oriented matroids reassessed
- Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
Cited in
(4)
This page was built for publication: Two-dimensional partial cubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q785580)
