Linear Algebra Methods in Combinatorics

The linear algebra method is a powerful technique that translates combinatorial problems into statements about vector spaces, matrices, and polynomials. By exploiting dimension arguments, one can obtain bounds that are difficult to achieve by purely combinatorial means.

Dimension Argument

Definition6.1Incidence Matrix

Given a set system $(X, \mathcal{F})$ where $X = \{x_1, \ldots, x_n\}$ and $\mathcal{F} = \{F_1, \ldots, F_m\}$ , the incidence matrix $M$ is the $m \times n$ matrix with entries $M_{ij} = 1$ if $x_j \in F_i$ and $M_{ij} = 0$ otherwise. The rank of $M$ over a field $\mathbb{F}$ provides bounds on $|\mathcal{F}|$ .

Definition6.2Characteristic Vector

For a subset $F \subseteq [n]$ , its characteristic vector $v_F \in \mathbb{F}^n$ is defined by $(v_F)_i = 1$ if $i \in F$ and $(v_F)_i = 0$ otherwise. For a family $\mathcal{F}$ , the vectors $\{v_F : F \in \mathcal{F}\}$ form a subset of $\mathbb{F}^n$ , and their linear independence over $\mathbb{F}$ implies $|\mathcal{F}| \leq n$ .

ExampleOddtown Theorem

In the town of Oddtown ( $n$ citizens), clubs satisfy: each club has an odd number of members, and any two distinct clubs share an even number of members. Then there are at most $n$ clubs. Proof: Over $\mathbb{F}_2$ , the characteristic vectors $v_{F_1}, \ldots, v_{F_m}$ satisfy $\langle v_{F_i}, v_{F_i} \rangle = |F_i| = 1$ and $\langle v_{F_i}, v_{F_j} \rangle = |F_i \cap F_j| = 0$ for $i \neq j$ (mod 2). So the vectors are linearly independent over $\mathbb{F}_2$ , giving $m \leq n$ .

The Polynomial Method

Definition6.3Combinatorial Nullstellensatz

Given a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ and finite subsets $S_1, \ldots, S_n \subseteq \mathbb{F}$ , if $f$ vanishes on all of $S_1 \times \cdots \times S_n$ and $\deg(f) = \sum_{i=1}^n (|S_i| - 1)$ , then the coefficient of the monomial $\prod_{i=1}^n x_i^{|S_i| - 1}$ in $f$ must be zero.

RemarkPower of the Method

The polynomial method bypasses the need for explicit constructions. By encoding a combinatorial problem as a polynomial vanishing condition, one can use algebraic constraints to derive combinatorial bounds. This method was pioneered by Alon and has since been refined into the polynomial partitioning technique by Guth and Katz.