Tournaments, Johnson Graphs, and NC-Teaching

Hans Ulrich Simon

TL;DR

This paper delves into the "No-Clash Teaching" (NC-Teaching) model, a framework for understanding how efficiently a teacher can convey concepts to a learner. The authors establish that NC-teaching dimension 1 concept classes are precisely those derived from tournaments, and they construct a family of concept classes that exhibit a striking separation between NC-teaching and recursive teaching dimensions, while also improving a key upper bound on the size of NC-teaching classes.

What Problem Does This Paper Address?

The paper tackles the problem of characterizing and bounding the complexity of concept classes within the "No-Clash Teaching" (NC-Teaching) model. This model, introduced recently, is considered optimal among collusion-free teaching models. A key question is understanding the structure of concept classes that are "NC-maximum" – meaning they are the largest possible classes for a given NC-teaching dimension and domain size. Specifically, the authors aim to:

  1. Characterize NC-maximum classes of dimension 1: What do these classes look like?
  2. Investigate the relationship between NC-teaching and Recursive Teaching Dimension (RTD): Can we find classes where RTD is high while NC-teaching is low, and vice-versa?
  3. Improve upper bounds on the size of NC-maximum classes: The existing bound of $2^d \binom{n}{d}$ for classes of dimension $d$ over domain size $n$ is known to be tight only for $d=1$. Can this bound be improved for $d > 1$?

Methods

The paper employs a combination of combinatorial graph theory and probabilistic methods:

  • Tournament-Induced Concept Classes: The authors define concept classes directly from tournaments. A tournament is a directed graph where every pair of vertices has exactly one directed edge between them. They show that NC-maximum classes of dimension 1 are precisely those that can be constructed this way.
  • Probabilistic Method and Random Tournaments: To demonstrate the existence of concept classes with a large RTD and a small NC-teaching dimension, they leverage the probabilistic method. They consider random tournaments and analyze the properties of the induced concept classes, specifically focusing on how easily they can be taught.
  • Johnson Graphs and Narrow Cliques: To improve the upper bound on the size of NC-maximum classes, the paper utilizes Johnson graphs. These graphs have sets of a fixed size as vertices, and edges connect sets that share a specific number of elements. The authors analyze subgraphs of Johnson graphs that do not contain "narrow cliques" of a certain size. This structural property is then linked to the NC-teaching dimension.

Datasets

Not discussed in the paper. The paper deals with abstract concept classes and theoretical bounds rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Tournaments as Building Blocks for Simple NC-Teaching: The surprising finding that NC-maximum classes of dimension 1 are directly characterized by tournaments provides a clean structural understanding for the simplest case of NC-teaching.
  • Striking Separation of RTD and NCTD: The construction of a family of concept classes where RTD grows logarithmically with class size, while NCTD remains constant at 1, is a significant result. This highlights a fundamental difference in the "difficulty" of teaching as perceived by these two models.
  • Johnson Graphs Reveal Structural Constraints: The use of Johnson graphs and the analysis of narrow cliques reveals a deeper combinatorial structure that limits the size of NC-maximum classes beyond the $d=1$ case. This leads to a tighter upper bound.

Key Results

  • NC-Maximum Classes of Dimension 1: A concept class over a domain of size $n$ is an NC-maximum class of NC-teaching dimension 1 if and only if it can be formed by taking all pairs of complementary concepts induced by a tournament with $n$ vertices.
  • RTD-NCTD Separation: There exists a family of concept classes $(\mathcal{C}_n)_{n\ge1}$ such that $|\mathcal{C}_n| = n$, $\text{RTD}(\mathcal{C}_n) = \Omega(\log n)$, and $\text{NCTD}(\mathcal{C}_n) = 1$ for all $n \ge 1$. This is achieved using random tournaments and the probabilistic method.
  • Improved Upper Bound: The paper improves the upper bound on the size of NC-maximum classes of dimension $d$ over a domain of size $n$ from $2^d \binom{n}{d}$ to approximately $\sqrt{d} \binom{n}{d}$. Specifically, for $d \ge 2$, $\text{MNC}(n, d) < 2^d \binom{n}{d}$.

Limitations and Future Work

  • Structure of Higher-Dimensional NC-Maximum Classes: While the structure of NC-maximum classes for dimension 1 is fully characterized, the paper acknowledges that the structural properties of NC-maximum classes for dimensions $d \ge 2$ remain unknown. This is posed as an open problem.
  • Exact Bounds on MNC(n, d): The paper provides improved upper bounds for $\text{MNC}(n, d)$ but does not determine the exact values for $d \ge 2$. Finding tighter bounds or exact values is suggested as future work.
  • Concrete Classes for RTD-NCTD Ratio: The proof for the RTD-NCTD separation relies on the probabilistic method, yielding non-constructive existence proofs. Finding a concrete, explicit concept class that achieves a large RTD-NCTD ratio (ideally logarithmic) is an open problem.

Summary updated

Abstract

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 $2^d \binom{n}{d}$ 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 $(\cC_n)_{n\ge1}$ of concept classes such that the well known recursive teaching dimension (= RTD) of $\cC_n$ grows logarithmically in $n = |\cC_n|$ while, for every $n\ge1$, the NC-teaching dimension of $\cC_n$ equals $1$. Since the recursive teaching dimension of a finite concept class $\cC$ is generally bounded $\log|\cC|$, the family $(\cC_n)_{n\ge1}$ separates RTD from NCTD in the most striking way. The proof of existence of the family $(\cC_n)_{n\ge1}$ makes use of the probabilistic method and random tournaments. Third, we improve the afore-mentioned upper bound $2^d\binom{n}{d}$ by a factor of order $\sqrt{d}$. The verification of the superior bound makes use of Johnson graphs and maximum subgraphs not containing large narrow cliques.
BibTeX
@inproceedings{simon2023tournaments,
  author = {Hans Ulrich Simon},
  title = {{Tournaments, Johnson Graphs, and NC-Teaching}},
  booktitle = {ALT},
  year = {2023},
  url = {https://openreview.net/forum?id=e8jBAR2Kud},
}
Figure