论文标题
比赛，约翰逊图和NC教学
Tournaments, Johnson Graphs, and NC-Teaching
论文作者
论文摘要
最近，有人提出了一种称为“无束缚教学”或简称为“ NC教学”的教学模型，在以下强烈的意义上是最佳的。首先，它满足了高盛和马蒂亚斯的勾结柔性条件。其次，相对于任何其他无碰撞教学模型，NC教学维度（= NCTD）小于或等于教学维度。还显示，任何具有NC教学尺寸$ d $的概念类，并在尺寸$ n $的域上定义最多可以拥有$ 2^d \ binom {n} {d} {d} $概念。本文的主要结果如下。首先，我们将NC教学尺寸$ 1 $的最大概念类表征为锦标赛（=完全定向图）以非常自然的方式引起的类。 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$.由于有限概念类$ \ cc $的递归教学维度通常是有限的$ \ log | \ cc | $，因此家庭$（\ cc_n）_ {n \ ge1} $以最震惊的方式将RTD与NCTD分开。家庭存在的证明$（\ cc_n）_ {n \ ge1} $使用了概率方法和随机锦标赛。第三，我们通过订单$ \ sqrt {d} $来改善上述上述上限$ 2^d \ binom {n} {d} $。上界的验证利用了约翰逊图和最大子图，不包含大狭窄集团。
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.
