VC-dimension of sets of permutations

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

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 languageEnglish (US)
Pages (from-to)241-255
Number of pages15
JournalCombinatorica
Volume20
Issue number2
DOIs
StatePublished - 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'VC-dimension of sets of permutations'. Together they form a unique fingerprint.

Cite this