Tournaments, Johnson Graphs and NC-Teaching

Some years ago 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. Specifically the NCTD is upper-bounded by the recursive teaching dimension (= RTD). This raised the question about the largest possible gap between the NCTD and the RTD. The main results in this paper are as follows. First, we show that there exists a family $({\mathcal{C}})_{n\ge1}$ of concept classes such that the RTD of ${\mathcal{C}}$ grows logarithmically in $n = |{\mathcal{C}}_n|$ while, for every $n\ge1$, the NCTD of ${\mathcal{C}}$ equals $1$. Since the RTD of a finite concept class ${\mathcal{C}}$ is generally bounded by $\log|{\mathcal{C}}|$, the family $({\mathcal{C}}_n)_{n\ge1}$ separates RTD from NCTD in the most striking way. Our first proof of existence of the family $({\mathcal{C}}_n)_{n\ge1}$ makes use of the probabilistic method and random tournaments. But we also present a concrete family of concept classes (leading to a slightly smaller lower bound on $\mathrm{RTD}({\mathcal{C}}_n)$) which makes use of so-called quadratic-residue tournaments. Second, we characterize the maximum concept classes of NCTD $1$ as classes which are induced by tournaments in a very natural way. Third, we improve the previously best upper bound on the size of a maximum class of NCTD $d$ by a factor of order $\sqrt{d}$. The verification of the new upper bound makes use of Johnson graphs and maximum subgraphs not containing large narrow cliques. The connections between tournaments, Johnson graphs and NC-Teaching revealed here were not known before and might be considered interesting in their own right.