Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 11 (Algebraic Methods in Combinatorics)

Use the pair-design convention: each pair of distinct points must lie in exactly one Steiner block of size $k$. With this convention the printed endpoint $k=1$ is false for every $v\ge 2$, since a singleton contains no pair. Thus the intended assertion requires $k\ge 2$. For $k=2$, take all pairs as Steiner blocks for any $v\ge 2$. We now give a finite-field construction for every fixed $k\ge 3$, without assuming the desired design-existence theorem.

Put $m=\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ and take an odd prime power $q\equiv 1(\mathrm{mod}2m)$. By cyclicity of ${\mathbb{F}}_q^{\times }$, it has a subgroup $H$ of index $m$; its order $(q-1)/m$ is even, so $-1\in H$. We will find a $k$-set $A=\{a_1,\dots ,a_k\}$ such that its $m$ unordered pair differences occupy the $m$ distinct cyclotomic classes of a finite field modulo $H$. The following argument supplies that set for every sufficiently large compatible $q$.

First establish the required two-class intersection estimate by elementary character sums. Let $\chi$ be a multiplicative character of a finite field of order $m$, with $\chi (\gamma )={\zeta }_m$ for a generator $\gamma$. Extend every power ${\chi }^j$, including the trivial character, by zero at zero. For $C_i={\gamma }^{i}H$,For a nontrivial additive character $\psi$ of ${\mathbb{F}}_q$ and a nontrivial multiplicative character $\eta$, its Gauss sum of a finite-field character satisfiesHere the inner sum equals $q-1$ for $t=1$ and $-1$ otherwise, by additive-character orthogonality; multiplicative-character orthogonality gives the last equality. Such a nontrivial additive character exists by identifying the additive group with a vector space over its prime field and choosing a nonzero linear functional into that prime field.

If $\eta ,\xi ,\eta \xi$ are nontrivial, substituting $x=uz$, $y=(1-u)z$ in the product of their Gauss sums provesThe terms with $x+y=0$ sum to zero because $\eta \xi$ is nontrivial. Hence $|J|=\sqrt{q}$. If exactly one character is trivial, subtracting the excluded zero and one terms gives absolute value one. If both are nontrivial but their product is trivial, the substitution $u/(1-u)$ gives $J(\eta ,{\eta }^{-1})=-\eta (-1)$, again of absolute value one. If both are trivial, the sum is $q-2$. Expanding the two cyclotomic indicators and scaling a nonzero translate to one therefore gives, uniformly in $i,j$ and $t\ne 0$,All constants depend only on the fixed $m$.

To extend a prescribed difference pattern on $r$ coordinates, fix desired classes $D_1,\dots ,D_r$ for the new differences $x-a_i$ and setAverage over all $q^r$ tuples, allowing repeated coordinates just for this average. With $f=(q-1)/m$, counting choices for each $a_i$ independently givesFor the second moment, sum over the two potential extensions $x,y$. The $x=y$ terms contribute $q{f}^r/q^r$. For $x\ne y$, the choices of $a_i$ number $q/m^2+O_m(\sqrt{q})$ each, by the preceding intersection estimate. ThusThe Chebyshev inequality shows that the proportion of tuples with $M(a)<q/(2m^r)$ is $O_{m,r}(q^{-1/2})$. Inductively, any fixed compatible difference pattern on $r$ distinct coordinates is realized by at least $c_r{q}^r$ tuples, with $c_r>0$ independent of sufficiently large $q$. The assertion starts with $r=1$. Almost all tuples are outside the exceptional set, so at least half the realizing tuples have at least $q/(2m^r)$ extensions. Each extension is distinct from the old coordinates because its differences belong to nonzero classes. This proves the assertion for $r+1$. This cyclotomic pattern extension by a second-moment bound avoids the false assumption that every partial choice can be extended.

Prescribe a different one of the $m$ cosets to each pair $a_j-a_i$, $i<j$. Since $-1\in H$, changing an orientation does not change its coset, so the prescriptions are compatible. The preceding induction supplies $A$.

Choose $S\subset H$ containing one element from each pair $\{h,-h\}$. Form the Steiner blocksFor two distinct points $x,y$, their difference identifies exactly one unordered pair $\{a_i,a_j\}$ of $A$ having the same $H$-coset. Exactly one of $(x-y)/(a_i-a_j)$ and its negative lies in $S$. Choose the orientation $a,b$ of that pair making $s=(x-y)/(a-b)\in S$, and then set $t=x-sa$. This yields $x=sa+t$, $y=sb+t$. Both the oriented base pair and $(s,t)$ are unique, so precisely one Steiner block contains the pair. In particular different Steiner block parameters cannot produce repeated Steiner blocks. Equivalently, the Steiner blocks $sA$ form a difference family for a Steiner 2-design, and translation gives the cyclotomic construction of a Steiner 2-design.

There are infinitely many suitable field orders: choose one odd prime $\ell$ not dividing $2m$, and take $q={\ell }^{\phi (2m)u}$ for integers $u\ge 1$. Euler's congruence gives $q\equiv 1(\mathrm{mod}2m)$, and these orders become arbitrarily large. ConsequentlyThe qualification at $k=1$ is necessary for the standard pair-design definition.

At any vertex, each complete bipartite graph $K_{k,k}$ containing it contributes exactly $k$ incident edges. Since the copies partition all incident edges of the complete graph, $n-1$ is a multiple of $k$. In particular $\gcd (n,k)=1$.

If there are $b$ copies, counting their edges givesThus $k^2\mid n(n-1)$. Since $n$ is coprime to $k^2$, it can be cancelled in this divisibility, yieldingIf $n=1$, the empty partition is consistent with the same conclusion, since every positive integer divides zero.

Let $G$ be a finite undirected $d$-regular graph on $N$ vertices, with adjacency matrix $A$ and normalized random walk matrix $P=A/d$. Define edge expansion and normalized conductance byAn expander family has orders tending to infinity, uniformly bounded maximum degree, and a uniform positive lower bound on $h$. For a regular graph the constant vector is an eigenvector of $P$ with eigenvalue one. Write its eigenvalues as $1={\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_N\ge -1$, and let $\delta =1-{\mu }_2$. This spectral gap measures the energetic cost of departing from a constant function.

For every mean-zero vector $f$, the spectral theorem and the graph's energy identity giveApply this to $f=1_S-|S|1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. ThereforeThus a uniform spectral gap gives uniform edge expansion when $d$ is fixed. This also bounds exterior vertex expansion: each exterior vertex accounts for at most $d$ boundary edges, so $|N(S)\setminus S|\ge e(S,S^c)/d$.

For the converse, take a mean-zero eigenvector $f$ for ${\mu }_2$ and choose its sign so that its positive support has at most $N/2$ vertices. Put $g=f^{+}$, which is nonzero. Truncation decreases energy in the following precise sense: for any two real numbers $a,b$,Summing over edges yields $⟨g,(I-P)g⟩\le ⟨g,(I-P)f⟩=\delta \Vert g{\Vert }_2^2$. For the threshold sets $S_t=\{v:g(v{)}^2>t\}$, every nonempty set lies in that small positive support. Integrating its boundary count gives the layer-cake identityThe Cauchy-Schwarz inequality bounds the left side bybecause the first sum is at most $d\delta \Vert g{\Vert }_2^2$ and the second at most $2d\Vert g{\Vert }_2^2$. Cancelling proves the Cheeger inequality in both directions:Hence bounded-degree regular families have uniform edge expansion exactly when their second-largest normalized eigenvalue stays uniformly below one.

Absolute eigenvalues give additional information. Put $\rho ={\max }_{i\ge 2}|{\mu }_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the expander mixing lemma:Here $e(S,T)=1_S^{T}A{1}_T$, so internal edges are counted as oriented incidences. A small $\rho$ makes edge counts resemble uniformly distributed edges. It also gives rapid random walk mixing: starting at a vertex, $P^t$ contracts the mean-zero component of its point mass by at most ${\rho }^t$ in Euclidean norm; Cauchy-Schwarz inequality then gives total variation distance at most $\frac{1}{2}\sqrt{N}{\rho }^t$ from the uniform distribution. A bipartite graph has eigenvalue $-1$ and its non-lazy walk alternates sides, even if it has good edge expansion. The lazy walk $(I+P)/2$ has nonconstant eigenvalues between zero and $1-\delta /2$, resolving this periodicity. It is important to distinguish the gap $1-{\mu }_2$ controlling cuts from the absolute bound controlling non-lazy mixing.

Here is a fully specified deterministic construction of an infinite family. Its degree is large but fixed. SetChoose the lexicographically first ordered list $a_1,\dots ,a_d\in W$ satisfyingThis finite deterministic search terminates. To prove existence, choose the list uniformly and independently. For each nonzero $u$, its signs are independent unbiased signs; the exponential-moment estimate $\cosh t\le e^{t^2/2}$ and Markov inequality give an exceptional probability at most $2e^{-d/200}$. A union bound gives total failure probability at mostThus at least one qualifying list exists. Fix it once and for all.

Let $H$ be the Cayley graph on $W$ whose $j$th neighbor of $x$ is $x+a_j$. It is an undirected $d$-regular port-labeled graph, allowing repeated edges and loops in this intermediate construction. Its characters $x\mapsto (-1{)}^{u\cdot x}$ form an orthogonal eigenbasis, with the displayed averages as normalized eigenvalues. Therefore $\rho (H)\le 1/10$. Each loop counts as one transition port; degrees here mean row sums of the adjacency matrix.

We next define the zig-zag product and prove the bound used for iteration. A port labeling of a $D_0$-regular undirected graph $F$ gives an involution ${\mathrm{Rot}}_F(v,a)=(w,b)$, recording the endpoint and reverse port. If a $d$-regular graph $H_0$ has vertex set $[D_0]$, the product has vertices $(v,a)\in V(F)\times [D_0]$. For each ordered pair of small-graph ports, move from $a$ to $a^{\prime }$ in $H_0$, follow the big edge ${\mathrm{Rot}}_F(v,a^{\prime })=(w,b^{\prime })$, and move from $b^{\prime }$ to $b$ in $H_0$. The endpoint is $(w,b)$; reversing the steps reverses the two small-graph port labels. The product is undirected, has $|V(F)|D_0$ vertices, and has degree $d^2$.

Write $B=I\otimes P_{H_0}$ and let $R$ be the permutation matrix of ${\mathrm{Rot}}_F$. The normalized product operator is $BRB$. For a mean-zero unit vector, decompose $f=u+v$ into its cloud-constant part and its cloud-orthogonal part. Then $Bu=u$, $\Vert Bv\Vert \le \rho (H_0)\Vert v\Vert$, and $\Vert R\Vert =1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|⟨u,Ru⟩|\le \rho (F)\Vert u{\Vert }^2$. Expanding the quadratic form and applying Cauchy-Schwarz inequality givesThe operator is symmetric, so its mean-zero operator norm is bounded by this same quantity. No unproved product spectral estimate is needed.

Start with the loop-inclusive complete graph $G_0$ on $D$ vertices, whose normalized matrix is $J/D$ and whose nonconstant eigenvalues are all zero. Given a $D$-regular $G_t$, its two-step graph $G_t^2$ has degree $D^2$ and normalized operator $P_{G_t}^2$. Label a two-step edge by its ordered pair of ports; reversal reverses the path and its reverse ports. These $D^2$ labels are the vertex set of the fixed graph $H$. DefineIt has degree $d^2=D$, and its number of vertices is $N_{t+1}=N_t{D}^2$, hence $N_t=D^{2t+1}$. By the proved bound,Starting from zero, induction gives $\rho (G_t)\le 1/2$, since $(1/2{)}^2+21/100=46/100<1/2$. The cut-energy argument therefore gives multiplicity-counted edge expansion at least $D/4$ for every $G_t$.

To obtain ordinary simple graphs, delete loops and merge parallel edges. The maximum degree is at most $D$, and any one unordered vertex pair had multiplicity at most $D$. Thus every cut retains at least $1/D$ of its multiplicity-counted boundary, givingThese simple graphs form an expander family. Every choice is deterministic: the finite base search is fixed independently of $t$, and the recursive edge rules determine all subsequent adjacency lists. Once that base is fixed, adjacency lists can be generated successively using the previous lists, with a constant amount of work per output edge. This is squaring and zig-zag iteration yields bounded-degree expanders. The spectral argument supplies the uniform expansion guarantee and explains why squaring improves the eigenvalues while the product restores a constant degree.

The coefficient form of the Combinatorial Nullstellensatz is as follows. Let $F$ be a field, let $P\in F[x_1,\dots ,x_r]$ have total degree at most $t_1+\cdots +t_r$, and suppose the coefficient of $x_1^{t_1}\cdots x_r^{t_r}$ is nonzero. For finite subsets $S_i\subset F$ with $|S_i|>t_i$, there is a point of $S_1\times \cdots \times S_r$ where $P$ is nonzero.

For completeness, restrict to $|S_i|=t_i+1$. The coefficient identity isBy Lagrange interpolation, the one-variable weighted sum on the right kills powers below $t_i$ and equals one on the power $t_i$. Any monomial of total degree at most $\sum t_i$, other than the specified one, has some exponent below $t_i$ and therefore contributes zero; the specified monomial contributes its coefficient. Every denominator is nonzero in the field. Hence a nonzero coefficient forces a nonzero grid value. The two applications below use this coefficient form.

Choose a fixed prime $p\ge k$, and put $s=2p-2$. We first derive the polynomial step: a graph $H$ on $N$ vertices and $M>(p-1)N$ edges, with maximum degree at most $2p-1$, contains a nonempty $p$-regular subgraph. Use a Boolean variable $x_e$ for each edge and work over ${\mathbb{F}}_p$. DefineThe first product has degree at most $(p-1)N<M$, while the full squarefree monomial ${\prod }_e{x}_e$ has coefficient $(-1{)}^{M+1}\ne 0$ in the second term with its minus sign. The Combinatorial Nullstellensatz, with every grid $\{0,1\}$, gives a nonzero value of $R$. Since $R(0)=0$, this is a nonempty edge selection. The second product is then zero, so the first is nonzero. Fermat's little theorem makes each selected vertex degree zero modulo $p$. The maximum-degree bound implies that every positive selected degree is precisely $p$. This proves the prime-regular subgraph from Boolean polynomial constraints.

We next turn density into an almost-regular bipartite subgraph, keeping the logarithmic loss explicit. Let the original graph have $n\ge 2$ vertices and $m>0$ edges. Some bipartition retains at least $m/2$ edges: choose the sides independently with probability $1/2$ and average the number crossing. Its average degree is at least $m/n$. Repeatedly delete a vertex of degree at most half the current average degree. Such a deletion cannot lower that average, sinceThe process cannot delete the last positive-density graph, because the maintained average is positive. At termination the minimum degree is an integer $\sigma >m/(2n)$.

Choose the larger side $A$ of this remaining bipartite graph, with opposite side $B$. Keep exactly $\sigma$ edges at each vertex of $A$; choices at different vertices of $A$ do not conflict. Remove any now-isolated vertices of $B$. Thus $|A|\ge |B|$, and every vertex of $A$ has degree $\sigma$.

Such a half-regular graph contains a half-regular restriction with a perfect matching. Choose a minimal nonempty $X\subseteq A$ satisfying $|N(X)|\le |X|$, which exists because the whole side $A$ satisfies this inequality. In fact equality holds: if it were strict, deleting a vertex of $X$ would retain the inequality, contradicting minimality; the singleton case has at least one neighbor. Every proper subset $Y\subset X$ satisfies $|N(Y)|\ge |Y|$. Hall's marriage theorem therefore supplies a perfect matching on $X\cup N(X)$. All $\sigma$ edges incident with each vertex of $X$ remain inside that restriction.

Delete this perfect matching and repeat the restriction argument. The left degrees decrease by one at each step. We obtain $\sigma$ edge-disjoint perfect matchings $M_0,\dots ,M_{\sigma -1}$ on nested nonempty vertex sets, with sizesFor any $i$ with $i+s\le \sigma -1$, the union of $s+1=2p-1$ consecutive matchings in a graph has maximum degree at most $2p-1$ and at least $(s+1)N_{i+s}/2$ edges on $N_i$ vertices. Ifit has more than $(p-1)N_i$ edges, so the polynomial step yields a $p$-regular bipartite subgraph. Every regular bipartite graph decomposes into perfect matchings: for a set in one part, counting incident edges gives Hall's inequality, so a perfect matching exists; remove it and repeat. Choosing $k$ of these $p$ matchings in a graph gives a nonempty $k$-regular subgraph. This is the nested matching criterion for a regular subgraph.

If no $k$-regular subgraph exists, every displayed size ratio must therefore satisfy the reverse inequality. Iterating at indices $0,s,2s,\dots$ gives, with $r=\lfloor (\sigma -1)/s\rfloor$,Consequently $r\le \log n/\log ((s+1)/s)$ andCombining with $\sigma >m/(2n)$ proves the required edge bound. For example the finite constantworks for every $n\ge 2$, and the case $n=1$ has no edges. ThusThe logarithm comes from how often a nested matching in a graph vertex set can shrink by a fixed factor before becoming empty; it is not supplied by the polynomial step alone.

Write $a=|A|$ and $b=|B|$, so $p\ge a>b\ge 1$. To cover both the unsaturated and saturated cases with the same coefficient calculation, setChoose $B^{\prime }\subseteq B$ of size $b^{\prime }$. These parameters satisfy $1\le b^{\prime }<a\le p$ and $1\le r\le p$.

Assume, for a contradiction, that the restricted sumset $C$ has fewer than $r$ elements. Extend it to a subset $D\subseteq {\mathbb{F}}_p$ of size $r-1$, and formOn $A\times B^{\prime }$, this polynomial vanishes: when $x=y$ the first factor vanishes, and when $x\ne y$ the sum belongs to $C\subseteq D$. Its total degree is $r=(a-1)+(b^{\prime }-1)$. Only the leading homogeneous part $(x-y)(x+y{)}^{r-1}$ contributes to the coefficient of $x^{a-1}{y}^{b^{\prime }-1}$. That coefficient isThe equality includes $b^{\prime }=1$, with an out-of-range binomial coefficient interpreted as zero. All factorial arguments are between zero and $p-1$, and $0<a-b^{\prime }<p$, so this coefficient is nonzero in ${\mathbb{F}}_p$. The Combinatorial Nullstellensatz applied to $A\times B^{\prime }$ forces a nonzero value, contradicting the vanishing just proved. Hence the restricted sumset bound for unequal subsets of a prime field isThe strict size inequality is used precisely in the nonzero factor $a-b^{\prime }$. The argument includes $r=p$ without dividing by $p!$, so no separate saturation assumption is hidden.