Advanced Combinatorics: Probabilistic Method + Algebraic Method

The two workhorses. UNION BOUND: if bad events $B_1, \dots, B_m$ have $\sum \Pr[B_i] < 1$, then with positive probability NONE occur — an object avoiding all bad properties exists. EXPECTATION: some outcome achieves at least (and some at most) the average, so computing $\mathbb{E}[X]$ by linearity proves an object with $X \ge \mathbb{E}[X]$ exists. Linearity is the entire engine: it needs NO independence, so you decompose $X$ into indicator variables, sum their individual probabilities, and never touch a joint distribution.

The canonical opener: every 2-coloring question. Color randomly, compute the expected number of monochromatic structures, and if that expectation is below 1 there is a coloring with ZERO — the classic bound that $K_n$ admits a 2-coloring with no monochromatic $K_k$ when $\binom{n}{k} 2^{1 - \binom{k}{2}} < 1$ (Erdős 1947, three lines, launched the field). The same skeleton handles tournaments, hypergraph colorings, and sum-free subsets ('every set of $n$ nonzero integers has a sum-free subset of size $> n/3$' — random dilation, expectation, done).

The deletion refinement handles expectations slightly TOO big: choose randomly, let bad events happen, then DELETE one element per bad event and count what survives — existence with a weaker but still nontrivial bound. Recognize the family: 'show there exists a subset/coloring/tournament with property P' where P resists explicit construction. Randomness is your construction.

Pitfall. Concluding 'a random object HAS the property' from a positive-probability argument. The method proves EXISTENCE; the random object merely might work. Keep the conclusion existential and the write-up earns full marks — one sloppy quantifier and it doesn't.

The template: encode combinatorial objects as vectors in a space whose dimension you know; show the vectors are linearly independent; conclude there are at most $\dim$ of them. All the content lives in ONE inner-product computation — typically $\langle v_i, v_j \rangle$ behaves differently for $i = j$ than $i \ne j$, and that asymmetry forces independence (test a dependence $\sum c_i v_i = 0$ against each $v_j$).

The signature results run on intersection parities. Oddtown: if every club has an ODD number of members and every two clubs share an EVEN number, then over $\mathbb{F}_2$ the incidence vectors satisfy $\langle v_i, v_i \rangle = 1$, $\langle v_i, v_j \rangle = 0$ — orthonormal-ish, hence independent, hence at most $n$ clubs from $n$ people. Fisher's inequality and set-pair bounds are the same three lines with different fields. The choice of FIELD is a real decision: parity conditions want $\mathbb{F}_2$; 'divisible by $p$' wants $\mathbb{F}_p$; distance conditions in geometry want $\mathbb{R}$ and polynomials as the vectors.

The polynomial-space variant is the modern upgrade: associate to each object a polynomial, show the polynomials are independent in a space of known dimension (spanned by few monomials), and the object count is bounded by the monomial count. This is how the two-distance-set bound and half of recent 'algebraic combinatorics' contest problems run — the vectors do not have to be 0-1 incidence strings; functions work.

Pitfall. Working over the wrong field. Over $\mathbb{R}$, self-inner-products of 0-1 vectors are SIZES, not parities — the odd/even hypotheses only become clean algebra in $\mathbb{F}_2$. Match the field to the arithmetic in the hypotheses before writing anything.

Selection heuristics. Probabilistic: the target is an INEQUALITY ('at least half', 'more than $n/3$'), the objects are colorings/subsets/orderings, and small cases show many valid objects (abundance is what randomness detects). Algebraic: the target is an EXACT BOUND ('at most $n$'), the hypotheses are exact arithmetic conditions (parities, prescribed intersection sizes, fixed distances), and small cases show the extremal configurations are rigid. Abundance → randomize; rigidity → linear algebra.

Both methods have a write-up trap of the same shape: the magic is front-loaded, so the FRAMING must be explicit. For probability: name the sample space and the random choice precisely ('color each vertex independently, uniformly'). For algebra: name the vector space, the field, and the encoding before any computation. Graders at this level dock the setup, not the arithmetic — the arithmetic is three lines in both methods.

These are also this phase's A3-B4 recognition targets: the phrases 'show there exists', 'show at most', 'any $n$ objects satisfying [exact condition]' should now trigger a deliberate method choice from this week's pair, alongside the classical tools. Add both templates to the toolbox card with one worked instance each — the methods are short enough that ONE fully internalized example each is genuine ownership.

Pitfall. Using $\le \mathbb{E}$ when you argued $\ge \mathbb{E}$ (or vice versa). 'Some outcome meets the average' cuts both ways, but each PROBLEM needs a specific direction — one clause in the write-up, one dropped point if missing.