Minimum Tournaments with the Strong S_k-Property and Implications for Teaching
share
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 of this family in the recursive model of teaching, order of log|| 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 || for any concept class .
READ FULL TEXT