2019/06/11 by Victor Chepoi, Chepoi, Victor, Kolja Knauer +3
Computer Science · Engineering · Mathematics · #Advanced Banach Space Theory #Cellular Automata and Applications #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1906.04492
openalex publication_date 2019/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We investigate the structure of two-dimensional partial cubes, i.e., of\nisometric subgraphs of hypercubes whose vertex set defines a set family of\nVC-dimension at most 2. Equivalently, those are the partial cubes which are not\ncontractible to the 3-cube Q3 (here contraction means contracting the edges\ncorresponding to the same coordinate of the hypercube). We show that our graphs\ncan be obtained from two types of combinatorial cells (gated cycles and gated\nfull subdivisions of complete graphs) via amalgams. The cell structure of\ntwo-dimensional partial cubes enables us to establish a variety of results. In\nparticular, we prove that all partial cubes of VC-dimension 2 can be extended\nto ample aka lopsided partial cubes of VC-dimension 2, yielding that the set\nfamilies defined by such graphs satisfy the sample compression conjecture by\nLittlestone and Warmuth (1986). Furthermore we point out relations to tope\ngraphs of COMs of low rank and region graphs of pseudoline arrangements.\n