论文标题
最低限度的比赛，具有强大的$ s_k $ - property及其对教学的影响
Minimum Tournaments with the Strong $S_k$-Property and Implications for Teaching
论文作者
论文摘要
据说一场比赛具有$ s_k $ - property，如果对于任何一组$ k $的球员来说，还有另一个击败他们的球员。在1960年代和1970年代初期，拥有该物业的最低赛事的探索非常好。在本文中，我们定义了$ s_k $ -property的加强，我们将“强$ s_k $ - property”命名。我们首先表明，较弱的概念的几个基本结果对于更强的概念仍然有效（证明的相应修改仅需要额外及时）。其次，证明较强的概念在教学领域具有应用。具体来说，我们介绍了一个无限的概念班家庭，所有这些都可以在无策略的教学模型中以一个示例来教授，以便在教学的递归模型中教授该家族的$ \ cc $，$ \ log | \ cc | $的顺序需要许多例子。这是第一本提出具体且易于构建的概念类别的论文，将无束缚与教学模型分开，而不是恒定的因素。对数因素的分离是显着的，因为递归教学维度已知$ \ log | \ cc | $的任何概念类别$ \ cc $。
A tournament is said to have the $S_k$-property if, for any set of $k$ players, there is another player who beats them all. Minimum tournaments having this property have been explored very well in the 1960's and the early 1970's. In this paper, we define a strengthening of the $S_k$-property that we name "strong $S_k$-property". We show, first, that several basic results on the weaker notion remain valid for the stronger notion (and the corresponding modification of the proofs requires only little extra-effort). Second, it is demonstrated that the stronger notion has applications in the area of Teaching. Specifically, we present an infinite family of concept classes all of which can be taught with a single example in the No-Clash model of teaching while, in order to teach a class $\cC$ of this family in the recursive model of teaching, order of $\log|\cC|$ many examples are required. This is the first paper that presents a concrete and easily constructible family of concept classes which separates the No-Clash from the recursive model of teaching by more than a constant factor. The separation by a logarithmic factor is remarkable because the recursive teaching dimension is known to be bounded by $\log |\cC|$ for any concept class $\cC$.
