2022/05/05 by Hans Ulrich Simon, Simon, Hans U. · 1 citation
Computer Science · #Advanced Algebra and Logic #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #Machine Learning and Algorithms #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.2205.02792
openalex publication_date 2022/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Quite recently a teaching model, called "No-Clash Teaching" or simply "NC-Teaching", had been suggested that is provably optimal in the following strong sense. First, it satisfies Goldman and Matthias' collusion-freeness condition. Second, the NC-teaching dimension (= NCTD) is smaller than or equal to the teaching dimension with respect to any other collusion-free teaching model. It has also been shown that any concept class which has NC-teaching dimension d and is defined over a domain of size n can have at most 2d \binomnd concepts. The main results in this paper are as follows. First, we characterize the maximum concept classes of NC-teaching dimension 1 as classes which are induced by tournaments (= complete oriented graphs) in a very natural way. Second, we show that there exists a family (\cCn)n≥1 of concept classes such that the well known recursive teaching dimension (= RTD) of \cCn grows logarithmically in n = |\cCn| while, for every n≥1, the NC-teaching dimension of \cCn equals 1. Since the recursive teaching dimension of a finite concept class \cC is generally bounded log|\cC|, the family (\cCn)n≥1 separates RTD from NCTD in the most striking way. The proof of existence of the family (\cCn)n≥1 makes use of the probabilistic method and random tournaments. Third, we improve the afore-mentioned upper bound 2d\binomnd by a factor of order √(d). The verification of the superior bound makes use of Johnson graphs and maximum subgraphs not containing large narrow cliques.