This work studies the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is {three}. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. For $d >2$, similar but slightly less accurate statements hold. {The lower bounds improve over previous ones by Ben-David et al., and the upper bounds are novel.}

The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve.

The upper bound technique is also used to: (i) provide estimates on the number of classes of a given VC dimension, and the number of maximum
classes of a given VC dimension -- answering a question of Frankl from '89,
and (ii) design an efficient algorithm that provides an $O(N/\log(N))$ multiplicative approximation for the sign rank.

We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue of absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. We use this connection to prove the existence of a maximum class $C\subseteq\{\pm 1\}^N$ with VC dimension $2$ and sign rank $\tilde{\Theta}(N^{1/2})$. This answers a question of Ben-David et al.~regarding the sign rank of large VC classes. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.

We further describe connections to communication complexity, geometry,
learning theory, and combinatorics.

Additional results in this version:
(i) Estimates on the number of maximum VC classes (answering a question of Frankl from '89).
(ii) Estimates on the sign rank of large VC classes (answering a question of Ben-David et al. from '03).
(iii) An approximation algorithm for computing the sign rank and adiscussion about the computational complexity of computing the sign-rank.

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. For $d >2$, similar but slightly less accurate statements hold.

The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve. The upper bound technique also yields an efficient
algorithm that provides an $O(N/\log(N))$ multiplicative approximation for the sign rank (Bhangale and Kopparty proved that deciding if the sign rank is at most $3$ is NP-hard).

We also observe a general connection between sign rank and spectral gaps which is based on Forster's argument. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue of absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.

We further describe connections to communication complexity, geometry, learning theory, and combinatorics.

Added an approximation algorithm for sign rank, discussion of duality, and references.

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe connections to combinatorics, communication complexity and learning theory.

We also provide explicit examples of matrices with low VC dimension and high sign rank. Let $A$ be the $N \times N$ point-hyperplane incidence matrix of a finite projective geometry with order $n \geq 3$ and dimension $d \geq 2$. The VC dimension of $A$ is $d$, and we prove that its sign rank is larger than $N^{\frac{1}{2}-\frac{1}{2d}}$. The large sign rank of $A$ demonstrates yet another difference between finite and real geometries.

To analyse the sign rank of $A$, we introduce a connection between sign rank and spectral gaps, which may be of independent interest. Consider the $N \times N$ adjacency matrix of a $\Delta$ regular graph with a second eigenvalue in absolute value $\lambda$ and $\Delta \leq N/2$. We show that the sign rank of the signed version of this matrix is at least $\Delta/\lambda$. A similar statement holds for all regular (not necessarily symmetric) sign matrices. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem.