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 条

[11] COMPLETENESS IN ORIENTED MATROIDS
FENTON, WE
DISCRETE MATHEMATICS, 1987, 66 (1-2) : 79 - 89
[12] Patchworking oriented matroids
Celaya, Marcel
Loho, Georg
Yuen, Chi Ho
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 2022, 106 (04): : 3545 - 3576
[13] Triangulations of oriented matroids
Santos, F
MEMOIRS OF THE AMERICAN MATHEMATICAL SOCIETY, 2002, 156 (741) : 1 - +
[14] ON THE COORDINATIZATION OF ORIENTED MATROIDS
BOKOWSKI, J
STURMFELS, B
DISCRETE & COMPUTATIONAL GEOMETRY, 1986, 1 (04) : 293 - 306
[15] Kirchberger's theorem for complexes of oriented matroids
Hochstaettler, Winfried
Keip, Sophia
Knauer, Kolja
LINEAR ALGEBRA AND ITS APPLICATIONS, 2024, 693 : 288 - 296
[16] The Signed Varchenko Determinant for Complexes of Oriented Matroids
Hochstaettler, Winfried
Keip, Sophia
Knauer, Kolja
COMBINATORICA, 2025, 45 (02)
[17] Cell complexes, oriented matroids and digital geometry
Webster, J
THEORETICAL COMPUTER SCIENCE, 2003, 305 (1-3) : 491 - 502
[18] COMPLEMENTARITY IN ORIENTED MATROIDS
TODD, MJ
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (04): : 467 - 485
[19] Oriented Matroids Today
Ziegler, Guenter M.
ELECTRONIC JOURNAL OF COMBINATORICS, 1998,
[20] Joins of oriented matroids
Hochstaettler, Winfried
Nickel, Robert
EUROPEAN JOURNAL OF COMBINATORICS, 2011, 32 (06) : 841 - 852

← 1 2 3 4 5 →