Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 109 (Combinatorics)

Proceed by mathematical induction on $n$. The cases $n=0,1$ are immediate. Given a symmetric chain decomposition of a Boolean lattice $\mathcal{P}([n-1])$, consider one of its chainsIt produces the two chainsand, when nonempty,The first runs from rank $r$ to rank $n-r$, and the second from rank $r+1$ to rank $n-1-r$; both endpoint ranks sum to $n$. They are disjoint and together contain the old chain both without and with $n$. Doing this for every old chain partitions $\mathcal{P}([n])$ into symmetric chains.

Choose symmetric chain decompositions of $\mathcal{P}(X_1)$ and $\mathcal{P}(X_2)$. Their Cartesian products partition $\mathcal{P}(X)$ into grids $C_1\times C_2$. Within one grid, two members in the same row differ only in $X_1$, and two in the same column differ only in $X_2$. The hypothesis on $\mathcal{F}$ therefore permits at most one member in each row and each column. Hence

Because $n_1$ and $n_2$ are even, both symmetric chains have odd length and are centred at ranks $n_1/2$ and $n_2/2$. The grid contains exactly $\min \{|C_1|,|C_2|\}$ points whose two ranks sum to $n/2$: they lie on its central antidiagonal. Thus the bound for $\mathcal{F}$ in each grid is the number of rank-$n/2$ subsets in that grid. Summing over all grids gives

For a sequence $J$ in ${\mathbb{F}}_p^2$, write $(r\mid J)$ for the number of $r$-term subsequences whose sum is zero. We use the following consequence of the Chevalley-Warning theorem: if $|J|=3p-1$, thenIndeed, with one variable $x_i$ for each term $(a_i,b_i)$, apply Chevalley--Warning toTheir degree sum is $3(p-1)<3p-1$. A common zero has support of size $0,p$, or $2p$ modulo $p$, and each fixed support contributes $(p-1{)}^{|S|}$ assignments. Reducing modulo $p$ gives the displayed congruence.

Now let the given $3p$ terms have total sum zero. If no $p$ of them summed to zero, delete any one term and apply the congruence to the remaining $3p-1$ terms. It givesso those remaining terms contain a zero-sum $2p$-subsequence. Its complement in the original $3p$ terms has size $p$ and sum zero, contradicting the assumption. Therefore the required $p$ terms exist.

We use the coefficient form of the Combinatorial Nullstellensatz: if a polynomial of degree ${\sum }_i{t}_i$ has nonzero coefficient at ${\prod }_i{x}_i^{t_i}$, then it cannot vanish on every product set ${\prod }_i{S}_i$ with $|S_i|>t_i$.

Write the terms as $(a_i,b_i)$ and, over ${\mathbb{F}}_p$, putandConsiderA direct multinomial-coefficient calculation, using Wilson's theorem, shows that the coefficient of ${\prod }_{i=1}^{4p-2}{x}_i$ in $F$ is nonzero. The Combinatorial Nullstellensatz with every $S_i=\{0,1\}$ therefore gives an indicator vector $x$ for which $F(x)\ne 0$.

The zero indicator does not work. The first two factors force the selected vectors to have both coordinate sums zero. If the support size is not divisible by $p$, Fermat's little theorem makes $1-S^{p-1}=0$, while the final product also vanishes; hence the support has size $p$, $2p$, or $3p$. Size $p$ proves the claim, and size $3p$ reduces to part (a). For size $2p$,so the bracket vanishes, again contradicting $F(x)\ne 0$. Only the size-$p$ and reducible size-$3p$ cases remain, and either yields the required zero-sum $p$-subsequence.

Let $D(a)$ denote the stated constant term and suppose every $a_i>0$. The rational identitycan be verified after clearing denominators, or by Lagrange interpolation. Multiplying it by the Dyson product and taking constant terms gives the recursionThe multinomial coefficientobeys the same recursion by the multinomial form of Pascal's identity.

If $a_k=0$, taking the constant term in $X_k$ forces the zero term from every factor involving $X_k$ and reduces the expression to the $(n-1)$-variable Dyson product with $a_k$ omitted. The same boundary reduction holds for $M(a)$. Finally $D(0,\dots ,0)=M(0,\dots ,0)=1$. Induction on $n$ and on $a_1+\cdots +a_n$ therefore proves the Dyson constant-term identity

Identify the additive group $G$ with the finite field ${\mathbb{F}}_q$, where $q=p^{\gamma }$. The sets $A$ and $B$ each have size $k<p$, and the field has odd characteristic. The Snevily matching theorem for an elementary abelian group states precisely that for two $k$-element subsets of the additive group of such a field, there is a bijection $\pi :A\to B$ for which the sums $a+\pi (a)$ are pairwise distinct.

For context, its polynomial proof antisymmetrizes the Vandermonde polynomialover all orderings of $B$. The coefficient furnished by the Dyson constant-term identity is a nonzero multiple of $k!$; it cannot vanish because $k<p$. Therefore at least one ordering $(b_1,\dots ,b_k)$ makes the Vandermonde product nonzero, which says exactly that

Assume (i). An antipodal map $g:S^n\to S^{n-1}$, followed by the inclusion $S^{n-1}\subset {\mathbb{R}}^n$, would be an antipodal map with no zero. Hence (i) implies (ii). Conversely, if an antipodal $f:S^n\to {\mathbb{R}}^n$ had no zero, thenwould be an antipodal map to $S^{n-1}$. Thus (ii) implies (i).

If $F:B^n\to S^{n-1}$ is antipodal on the boundary, regard $S^n$ as two copies of $B^n$ glued along their boundary. Use $F(x)$ on the upper copy and $-F(-x)$ on the lower copy. The boundary condition makes these definitions agree on the seam, and the resulting map $S^n\to S^{n-1}$ is antipodal. Thus (ii) implies (iii).

Conversely, an antipodal map $g:S^n\to S^{n-1}$ restricted to a closed hemisphere, identified with $B^n$, is antipodal on its equatorial boundary. Hence (iii) implies (ii). The three assertions are equivalent; they are standard forms of the Borsuk-Ulam theorem.

For $v\in S^{n-1}$, orthogonally project every member of ${\mathcal{C}}_i$ onto the oriented line ${\ell }_v$. These projections are compact intervals. They are pairwise intersecting because the original sets are, and pairwise intersecting intervals have a common intersection. Let $m_i(v)$ be the midpoint of that common interval and let $f_i(v)$ be its signed coordinate on ${\ell }_v$. Compactness makes $f_i$ continuous, and reversing the orientation gives

Define the continuous antipodal mapThe Borsuk-Ulam theorem gives $v$ with $F(v)=0$. Write the common value as $t$. The hyperplanemeets every set in every ${\mathcal{C}}_i$, because $t=f_i(v)$ lies in the projection interval of each such set. Thus $H$ is the required common hyperplane transversal.