VC-dimension of sets of permutations (Q5928570)
From MaRDI portal
scientific article; zbMATH DE number 1583105
Language | Label | Description | Also known as |
---|---|---|---|
English | VC-dimension of sets of permutations |
scientific article; zbMATH DE number 1583105 |
Statements
VC-dimension of sets of permutations (English)
0 references
1 April 2001
0 references
The VC-dimension of a hypergraph \(H=(V,E)\) is the size of the largest \(U\subset V\) such that \(|\{U\cap e:e\in E\}|=2^{|U|}\), i.e. the traces of edges cut \(U\) in all possible ways. For a hypergraph \(H\) of VC-dimension \(k\), and \(|V|=n\) Sauer's lemma states that \(|E|\leq \sum_{i=0}^k {n \choose i}\). The author defines the VC-dimension for sets of permutations \(A \subset S_n\). This is equal to the size of the largest subset of indices, say \(\{i_1, \dots,i_k\}\), such that the restriction of \(A\) to this set would result in all linear orders. (There is an obvious link to Condorcet's celebrated paradox.) An analogon of Sauer's lemma is proven for sets of VC-dimension 2. Namely their size is smaller than \(c^n\) for an appropriate constant \(c\). Some questions are raised: 1. Is it true that there exists a constant \(c_k\) for any \(k \in N\), such that \(|A|<c_k^n\) for any set of dimension no more than \(k\)? 2. Is the smallest value for \(c_2\) equal to the Catalan number, that is \(c_2 = \frac{1}{n+1} {2n \choose n}\) suffices? There is an unproven claim, that instead of the bound \(c_k^n\), an \(O(\log n)^n\) bound might be shown by extending the method of the paper.
0 references
VC-dimension
0 references
Sauer's lemma
0 references
Condorcet paradox
0 references
acyclic orders
0 references
hypergraph
0 references
set of permutations
0 references