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 条
  • [21] Syzygies of oriented matroids
    Novik, I
    Postnikov, A
    Sturmfels, B
    DUKE MATHEMATICAL JOURNAL, 2002, 111 (02) : 287 - 317
  • [22] CONVEXITY IN ORIENTED MATROIDS
    LASVERGNAS, M
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 29 (02) : 231 - 243
  • [23] ON SIGN-INVARIANCE GRAPHS OF UNIFORM ORIENTED MATROIDS
    CORDOVIL, R
    DUCHET, P
    DISCRETE MATHEMATICS, 1990, 79 (03) : 251 - 257
  • [24] On the generation of oriented matroids
    Bokowski, J
    de Oliveira, AG
    DISCRETE & COMPUTATIONAL GEOMETRY, 2000, 24 (2-3) : 197 - 208
  • [25] Oriented Lagrangian matroids
    Booth, RF
    Borovik, AV
    Gelfand, IM
    White, N
    EUROPEAN JOURNAL OF COMBINATORICS, 2001, 22 (05) : 639 - 656
  • [26] BASES IN ORIENTED MATROIDS
    LASVERGNAS, M
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1978, 25 (03) : 283 - 289
  • [27] Games in oriented matroids
    McLennan, Andrew
    Tourky, Rabee
    JOURNAL OF MATHEMATICAL ECONOMICS, 2008, 44 (7-8) : 807 - 821
  • [28] On the Generation of Oriented Matroids
    J. Bokowski
    A. Guedes de Oliveira
    Discrete & Computational Geometry, 2000, 24 : 197 - 208
  • [29] Tropical Oriented Matroids
    Horn, Silke
    COMBINATORIAL METHODS IN TOPOLOGY AND ALGEBRA, 2015, 12 : 53 - 57
  • [30] ALGEBRAIC-VARIETIES CHARACTERIZING MATROIDS AND ORIENTED MATROIDS
    BOKOWSKI, J
    DEOLIVEIRA, AG
    RICHTERGEBERT, J
    ADVANCES IN MATHEMATICS, 1991, 87 (02) : 160 - 185
12345