The complexity of recognizing optimal set systems for the V-C dimension The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\mathcal S$ with $S_i\cap X'=X'_i$.

The following decision problem is then natural:


  VC DIMENSION
  Input: a set system $(X,\mathcal S)$ and an integer $k$.
  Task: decide whether the VC dimension of $(X,\mathcal S)$ is at least $k$.


Since there are $2^{|X'|}$ subsets of $X'$, we have $|X'|\leq\log_2(|\mathcal S|)$, and hence VC DIMENSION can be solved in time $O\binom{|X|}{\log_2(|\mathcal S|)}$. For the hardness side, VC DIMENSION is LOGNP-hard (see here). However, I wonder whether something is known for the following specific case:


  My question: what is the complexity of deciding whether a given set system $(X,\mathcal S)$ has VC dimension exactly $\log_2(|\mathcal S|)$?
This doesn't answer the question, but it might be helpful.  Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented:

On the Complexity of Approximating the VC Dimension
http://users.cms.caltech.edu/~umans/papers/MU01-final.ps