AMPLE COMPLETIONS OF ORIENTED MATROIDS AND COMPLEXES OF UNIFORM ORIENTED MATROIDS

被引：5
|
作者：
Chepoi, Victor [1 ,2 ]
Knauer, Kolja [1 ,2 ,3 ]
Philibert, Manon [1 ,2 ]
机构：
[1] Aix Marseille Univ, CNRS, LIS, F-13288 Marseille 9, France
[2] Univ Toulon & Var, Fac Sci Luminy, F-13288 Marseille 9, France
[3] Univ Barcelona, Dept Matemat & Informat, Barcelona 08007, Spain
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2022年 / 36卷 / 01期
关键词：
ample set systems; oriented matroids; partial cubes; sample compression;
D O I：
10.1137/20M1355434
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
This paper considers completions of tope graphs of complexes of oriented matroids (COMs) to ample partial cubes of the same Vapnik-Chervonenkis dimension (VC-dimension). We show that these exist for oriented matroids (OMs) and complexes of uniform oriented matroids (CUOMs). This implies that tope graphs of OMs and CUOMs satisfy the sample compression conjecture one of the central open questions of learning theory. We conjecture that the tope graph of every COM can be completed to an ample partial cube without increasing the VC-dimension.
引用
收藏
页码：509 / 535
页数：27
相关论文
共 50 条
  • [1] COMs: Complexes of oriented matroids
    Bandelt, Hans-Juergen
    Chepoi, Victor
    Knauer, Kolja
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2018, 156 : 195 - 237
  • [2] Total polynomials of uniform oriented matroids
    Lawrence, J
    EUROPEAN JOURNAL OF COMBINATORICS, 2000, 21 (01) : 3 - 12
  • [3] ORIENTED MATROIDS
    FOLKMAN, J
    LAWRENCE, J
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (02) : 199 - 236
  • [4] Modular elimination in matroids and oriented matroids
    Delucchi, Emanuele
    EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (03) : 339 - 343
  • [5] On Tope Graphs of Complexes of Oriented Matroids
    Knauer, Kolja
    Marc, Tilen
    DISCRETE & COMPUTATIONAL GEOMETRY, 2020, 63 (02) : 377 - 417
  • [6] On Tope Graphs of Complexes of Oriented Matroids
    Kolja Knauer
    Tilen Marc
    Discrete & Computational Geometry, 2020, 63 : 377 - 417
  • [7] UNIFORM ORIENTED MATROIDS WITHOUT THE ISOTOPY PROPERTY
    JAGGI, B
    MANILEVITSKA, P
    STURMFELS, B
    WHITE, N
    DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (02) : 97 - 100
  • [8] A characterization of cocircuit graphs of uniform oriented matroids
    Jos Montellano-Ballesteros, Juan
    Strausz, Ricardo
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (04) : 445 - 454
  • [9] On exchange properties for Coxeter matroids and oriented matroids
    Borovik, AV
    Gelfand, I
    White, N
    DISCRETE MATHEMATICS, 1998, 179 (1-3) : 59 - 72
  • [10] ADJOINTS OF ORIENTED MATROIDS
    BACHEM, A
    KERN, W
    COMBINATORICA, 1986, 6 (04) : 299 - 308
12345