Abstract
We define the VC-dimension of a set of permutations A ⊂ Sn to be the maximal k such that there exist distinct i1,...,ik ∈ {1,...,n} that appear in A in all possible linear orders, that is, every linear order of {i1,...,ik} is equivalent to the standard order of {π(i1),...,π(ik)} for at least one permutation π ∈ A. In other words, the VC-dimension of A is the maximal k such that for some i1,...,ik the restriction of A to {i1,...,ik} contains all possible linear orders. This is analogous to the VC-dimension of a set of strings. Our main result is that there exists a universal constant C such that any set of permutations A ⊂ Sn with VC-dimension 2 is of size < Cn. This is analogous to Sauer's lemma for the case of VC-dimension 2. One corollary of our main result is that any acyclic set of linear orders of {1,...,n} is of size < Cn, (a set A of linear orders on {1,...,n} is called acyclic if no 3 elements i, j, k ∈ {1,...,n} appear in A in all 3 orders (i, j, k), (k, i, j) and (j, k, i)). The size of the largest acyclic set of linear orders has interested researchers for many years because it is the largest number of linear orders of n alternatives such that the following is always satisfied: if each one of a set of voters chooses one of these orders as his preference then the majority relation between each two alternatives is transitive.
Original language | English (US) |
---|---|
Pages (from-to) | 241-255 |
Number of pages | 15 |
Journal | Combinatorica |
Volume | 20 |
Issue number | 2 |
DOIs | |
State | Published - 2000 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics