2025/02/13 by Hans Ulrich Simon, Simon, Hans U. · 2 citations
Computer Science · #68R05 (primary) 05C99 (secondary) #Discrete Mathematics (cs.DM) #F.1.3 #FOS: Computer and information sciences #G.2.1 #I.2.6 #Rough Sets and Fuzzy Logic #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.2502.09453
openalex publication_date 2025/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is conjectured that the recursive teaching dimension of any finite concept class is upper-bounded by the VC-dimension of this class times a universal constant. In this paper, we confirm this conjecture for two rich families of concept classes where each class is induced by some graph G. For each G, we consider the class whose concepts represent stars in G as well as the class whose concepts represent connected sets in G. We show that, for concept classes of this kind, the recursive teaching dimension either equals the VC-dimension or is less by 1.