Two-dimensional partial cubes

DOI10.37236/8934MaRDI QIDQ785580zbMATH OpenOpenAlexFDO

Authors Victor Chepoi, Kolja Knauer, Manon Philibert

Publication date 7 August 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1906.04492

zbMATH Keywords

gated cyclesgated full subdivisions of complete graphs

Mathematics Subject Classification ID

Distance in graphs (05C12)

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 $Q_3$ (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.

Review text

Summary: 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 \(Q_3\) (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 \textit{N. Littlestone} and \textit{M. Warmuth} [``Relating data compression and learnability, Preprint] in a strong sense. The latter is a central conjecture of the area of computational machine learning, that is far from being solved even for general set systems of VC-dimension 2. Moreover, we point out relations to tope graphs of COMs of low rank and region graphs of pseudoline arrangements.

Recommendations

• Partial cubes: Structures, characterizations, and constructions
• Ample completions of oriented matroids and complexes of uniform oriented matroids
• Convexity in partial cubes: the hull number

Cites work

• A combinatorial problem; stability and order for models and theories in infinitary languages
• Basic phylogenetic combinatorics.
• Bounding embeddings of VC classes into maximum classes
• Cellular bipartite graphs
• Combinatorics of lopsided sets
• COMs: complexes of oriented matroids
• 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
• 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?)
• 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 density of families of sets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• 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 axiomatization of affine oriented matroids reassessed
• The Varchenko determinant for oriented matroids
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements

Cited in

(6)

• scientific article; zbMATH DE number 5502208 (Why is no real title available?)
• Ample completions of oriented matroids and complexes of uniform oriented matroids
• Corners and simpliciality in oriented matroids and partial cubes
• Labeled sample compression schemes for complexes of oriented matroids
• Geometry of convex geometries
• Using oriented matroids to bound the monotone rank of a matrix

Describes a project that uses

Uses Software

• AMPL

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)