VC-dimension of sets of permutations (Q5928570)

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.