Unlabeled sample compression schemes for oriented matroids

被引：0
作者：
Marc, Tilen [1 ,2 ]
机构：
[1] Fac Math & Phys, Ljubljana, Slovenia
[2] Inst Math Phys & Mech, Ljubljana, Slovenia
来源：
DISCRETE MATHEMATICS | 2024年 / 347卷 / 07期
关键词：
Compression schemes; Oriented matroids; Tope graphs; VC-dimension; Oriented matroid programs; Partial cubes; COMPLEXES;
D O I：
10.1016/j.disc.2024.114006
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A long-standing sample compression conjecture asks to linearly bound the size of the optimal sample compression schemes by the Vapnik-Chervonenkis (VC) dimension of an arbitrary class. In this paper, we explore the rich metric and combinatorial structure of oriented matroids (OMs) to construct proper unlabeled sample compression schemes for the classes of topes of OMs bounded by their VC -dimension. The result extends to the topes of affine OMs, as well as to the topes of the complexes of OMs that possess a corner peeling. The main tool that we use are the solutions of certain oriented matroid programs. (c) 2024 Elsevier B.V. All rights reserved.
引用
收藏
页数：13
相关论文
共 20 条
[1]   COMs: Complexes of oriented matroids [J].
Bandelt, Hans-Juergen ;
Chepoi, Victor ;
Knauer, Kolja .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2018, 156 :195-237
[2]   Cellular bipartite graphs [J].
Bandelt, HJ ;
Chepoi, V .
EUROPEAN JOURNAL OF COMBINATORICS, 1996, 17 (2-3) :121-134
[3]   Combinatorics of lopsided sets [J].
Bandelt, HJ ;
Chepoi, V ;
Dress, A ;
Koolen, J .
EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (05) :669-689
[4]   GRAPHS WITH INTRINSIC S3 CONVEXITIES [J].
BANDELT, HJ .
JOURNAL OF GRAPH THEORY, 1989, 13 (02) :215-228
[5]   Combinatorial variability of Vapnik-Chenvonenkis classes with applications to sample compression schemes [J].
Ben-David, S ;
Litman, A .
DISCRETE APPLIED MATHEMATICS, 1998, 86 (01) :3-25
[6]  
Bjorner A., 1999, Encyclopedia of Mathematics and its Applications, V46
[7]   Unlabeled sample compression schemes and corner peelings for ample and maximum classes [J].
Chalopin, Jeremie ;
Chepoi, Victor ;
Moran, Shay ;
Warmuth, Manfred K. .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2022, 127 :1-28
[8]  
Chepoi V, 2022, Arxiv, DOI arXiv:2110.15168
[9]   AMPLE COMPLETIONS OF ORIENTED MATROIDS AND COMPLEXES OF UNIFORM ORIENTED MATROIDS [J].
Chepoi, Victor ;
Knauer, Kolja ;
Philibert, Manon .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2022, 36 (01) :509-535
[10]   Hypercellular graphs: Partial cubes without Q3- as partial cube minor [J].
Chepoi, Victor ;
Knauer, Kolja ;
Marc, Tilen .
DISCRETE MATHEMATICS, 2020, 343 (04)
12