Here are some examples where the dimension of a vector space of polynomials is used to solve a combinatorial problem.

**Theorem 1** There are at most $n(n+1)/2$ equiangular lines in $\mathbb{R}^n$.

Proof. [Koornwinder] Let $L_1, \dots, L_m$ be $m$ lines passing through origin in $\mathbb{R}^n$ with angle $\arccos(\alpha)$ between every pair of them. Pick unit vectors $u_1, \dots, u_m$ on each line. Then we have $\langle u_i, u_j \rangle ^2 = \alpha^2$ for all $i \neq j$, and $\langle u_i, u_i \rangle = 1$ for all $i$. Define polynomials $P_1, \dots, P_m$ with $P_i(x) = \langle u_i, x \rangle^2 - \alpha^2 \langle x, x \rangle$. Then we have $P_i(u_j) = (1-\alpha^2)\delta_{i, j}$, and therefore, these $m$ polynomials are linearly independent (unless $\alpha^2 = 1$, but this case is easy since $\mathbb{R}^n$ has no more than $n$ mutually orthogonal nonzero vectors). The space of $n$-variable *homogenous* polynomials with degree at most $2$ has dimension ${n + 1\choose 2}$, and therefore $m \leq n(n+1)/2$.

**Theorem 2** [Larman, Rogers, Seidel] A two-distance set in $\mathbb R^n$ has cardinality at most $(n+4)(n+1)/2$.

Proof. Let $u_1, \dots, u_m$ be $m$ points in $R^n$ and $a$, $b$ be the two non-zero real number such that $\|u_i - u_j\| \in \{a, b\}$. Define $P_i(x) = (\|u_i - x\|^2 - a^2)(\|u_i - x\|^2 - b^2)$. Then, $P_i(u_j) = a^2b^2\delta_{i, j}$. Therefore, the polynomials $P_i$'s are linearly independent. Moreover, these polynomials lie in the vector space spanned by polynomials of the type $$\left(\sum_{i = 1}^nx_i^2\right)^2, \left(\sum_{i = 1}^n x_i^2\right)x_j, x_ix_j, x_i, 1.$$
The number of such polynomials is $1 + n + n(n+1)/2 + n + 1 = (n+4)(n+1)/2$, which gives us the bound.

For more such examples see "Linear Algebra Methods in Combinatorics" by Babai and Frankl, linked in Stanley's answer.