Let $R$ be a semiring, and let $P\subseteq R[x_1,\ldots,x_n]$ be some set of polynomials. Associate with every pair $(x,z)\in R^{n+1}$ the $0$-$1$ function $F_{x,z}: P\to\{0,1\}$ defined by: $F_{x,z}(p)=1$ iff $p(x)=z$. Define the VC dimension of the set $P$ of polynomials to be the VC dimension of the family of all such functions $F_{x,z}$. That is, the VC dimension of of $P$ is the largest number $v$ for which there exist polynomials $p_1,\ldots,p_v$ in $P$ such that \[ \Big\{\big(F_{x,z}(p_1),\ldots, F_{x,z}(p_v) \big) \colon x\in R^n, z\in R\Big\} =\{0,1\}^v\,. \] Our goal is to prove the following theorem.
Theorem 1: Over any tropical semiring $R$, the VC dimension of polynomials of degree at most $d$ of $n$ variables is at most a constant times $n^2\log(n+d)$.Let $R$ be an ordered field. An algebraic formula $\Phi(x)$ of size $s$ and degree $d$ over $R$ is an arbitrary boolean combination of $s$ atomic predicates, each being of the form $\pred{p>0}$ or $\pred{p=0}$ or $\pred{p<0}$ for some polynomial $p\in R[x_1,\ldots,x_n]$ of degree at most $d$.
Theorem 2 Let $R$ be an ordered field, and let $\Phi(x,y)$ be an algebraic formula of $n+m$ variables over $R$. Let $\f$ be the family of all functions $F_x: R^m\to\{0,1\}$ defined by: $F_x(y)=1$ iff $\Phi(x,y)=1$. Then the VC dimension of $\f$ is at most $2n\log(\euler ks)$.See here for the proof.
Proof of Theorem 1: Let $(R,\max,+)$ be a tropical semiring with $R\subseteq \RR$, and let $P$ be the set of all polynomials in $R[x_1,\ldots,x_n]$ of degree at most $d$. (Thus, $R$ may be $\NN$ or $\ZZ$ or $\QQ$ or $\RR_+$ or $\RR$ etc. depending on what maximization problems we are interested in.) Each polynomial $p\in P$ is specified by some matrix $A=(a_{i,j})$ with $n+1$ columns of the form $A=[B|c]$, where the entries of the last column $c$ are from the semiring $R$, and the entries of $B$ are nonnegative integer numbers. The polynomial $p$ then has the form \[ p_{A}(x)=\max\{ \ell_{a}(x)\colon a \mbox{ is a row of } A\}\ \ \mbox{ where }\ \ \ell_{a}(x)=a_1x_1+\cdots+a_nx_n+ a_{n+1}\,. \] Since the degree of $p_A$ cannot exceed $d$, the number of distinct rows $b$ of the submatrix $B$ cannot exceed the number of nonnegative integer solutions $z\in \NN^n$ of $z_1+\cdots+z_n\leq d$. The number of nonnegative integer solutions $z\in \NN^n$ of an equation $z_1+\cdots+z_n=r$ is exactly $\binom{n+r-1}{r}$. Hence, the number of distinct rows in $A$ cannot exceed \[ m:= \sum_{r=0}^d \binom{n+r-1}{r} =\binom{n+d}{d} = \binom{n+d}{n} \leq (n+d)^n\,. \] Let $\f$ be the family of all functions $F_{x,z}: P\to\{0,1\}$ defined by: $F_{x,z}(p)=1$ iff $p(x)=z$. Our goal is to show that the VC dimension of the family $\f$ of all such function $F_{x,z}$ is at most about $n^2\log(n+d)$.
We are going to apply Theorem 2. Let $Y=(y_{i,j})$ be an $m\times (n+1)$ matrix of indeterminates, and consider the following algebraic formula \[ \Phi(x,Y,z)=\bigg(\bigvee_{y\ \mathrm{row\ of}\ Y} [\ell_{y}(x)-z=0]\bigg)\land \bigwedge_{y\ \mathrm{row\ of}\ Y}[\ell_{y}(x)-z<0]\lor[\ell_y(x)-z=0]\,. \] Note that, for every $m\times (n+1)$ matrix $A$, we have \[ \mbox{$\Phi(x,A,z)=1$ $\iff$ $\max\{ \ell_{a}(x)\colon a \mbox{ is a row of } A\}=z$ $\iff$ $p_A(x)=z$ $\iff$ $F_{x,z}(p_A)=1$.} \] Thus, the formula $\Phi$ computes all functions in $\f$. Since the formula $\Phi$ has degree $k=2$ (all used polynomials $\ell_y(x)-z =x_1y_1+\cdots+x_ny_n+ y_{n+1}-z$ are quadratic) and size $s\leq 3m\leq 3(n+d)^n$ (at most so many distinct predicates are used), Theorem 2 implies that the VC dimension of $\f$ is at most $2n\log(\euler ks) = O(n\log s) = O(n^2\log(n+d))$. $\Box$