Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 13 (Topics in Combinatorics)

Let $P$ be the transition matrix of a finite irreducible Markov chain with at least two states, reversible with stationary distribution $\pi$. Its Dirichlet form of a Markov chain isThe Discrete Poincare inequality states that ${\mathrm{Var}}_{\pi }f\le C\mathcal{E}(f,f)$ for every real $f$. Its optimal constant is $C=(1-{\lambda }_2{)}^{-1}$, where ${\lambda }_2$ is the second largest eigenvalue of $P$. Indeed, detailed balance makes $P$ self-adjoint on $L^2(\pi )$. Expand $f-\pi (f)={\sum }_{j\ge 2}{a}_j{v}_j$ in an orthonormal eigenbasis. Then ${\mathrm{Var}}_{\pi }f=\sum a_j^2$ and $\mathcal{E}(f,f)=\sum (1-{\lambda }_j)a_j^2$, proving the inequality and its sharpness.

The useful constructive version is the canonical paths Poincare bound. Choose transition graph paths ${\gamma }_{xy}$ between each ordered pair, write $Q(u,v)=\pi (u)P(u,v)$, and definewhere $N_{uv}$ counts occurrences of the directed transition. The Cauchy-Schwarz inequality along each path in a graph gives $(f(x)-f(y){)}^2\le |{\gamma }_{xy}|{\sum }_{{\gamma }_{xy}}(f(u)-f(v){)}^2$. Multiply by $\pi (x)\pi (y)/2$ and sum. The identity ${\mathrm{Var}}_{\pi }f=\frac{1}{2}{\sum }_{x,y}\pi (x)\pi (y)(f(x)-f(y){)}^2$ proves ${\mathrm{Var}}_{\pi }f\le \rho \mathcal{E}(f,f)$.

For a lazy Markov chain this also proves the mixing time estimateTo see this, the centred initial density has $L^2(\pi )$ norm at most $\pi (x{)}^{-1/2}$; laziness puts all nonconstant eigenvalues between zero and $1-{\rho }^{-1}$. Their powers contract that norm, and the Cauchy-Schwarz inequality bounds total variation distance by half the density's $L^2(\pi )$ norm.

Here is a precise sufficient density condition for the permanent application: every row and every column has more than $n/2$ ones. Interpret the permanent of a matrix as the number $m_n$ of perfect matchings in its bipartite graph, with $n$ vertices per side. Write $m_k$ for the number of $k$-edge matchings in a graph.

First prove the short augmenting paths in a dense bipartite graph bound. Given a nonperfect matching in a graph, choose unmatched $u,v$ on opposite sides. If either has an unmatched neighbour, augment with one edge. Otherwise the matched partners of $N(u)$ and the neighbours $N(v)$ are subsets of the same $n$-element side whose total size exceeds $n$. Their intersection gives an alternating path in a graph $u,b,a,v$ of length three, with $ab$ a matching edge. Repeating proves $m_n>0$. Choose augmentations by a fixed deterministic rule. A reverse augmentation is specified by at most four vertices, so a next-size matching in a graph has at most $C_0=2n^4$ preimages. Therefore

Use the matching generating function $Z(\lambda )={\sum }_{k=0}^n{m}_k{\lambda }^k$ and the weighted matching Markov chain on all matchings in a graph, with stationary weights ${\pi }_{\lambda }(M)={\lambda }^{|M|}/Z(\lambda )$. It stays put with probability $1/2$; otherwise it chooses a graph edge uniformly and proposes its deletion, its addition if both endpoints are unmatched, or its exchange for the unique incident matching edge if precisely one endpoint is matched. Other proposals stay put. Accept with probability $\min (1,{\lambda }^{|M^{\prime }|-|M|})$. Reverse proposals use the opposite exchanged edge, so detailed balance holds. Deletions connect every state to the empty matching in a graph.

For completeness, the canonical paths for the weighted matching chain give a polynomial bound without assuming a mixing theorem. The symmetric difference $I△F$ consists of alternating graph paths and graph cycles. Order its components deterministically, orient open components from their smaller endpoint, and convert them from $I$ to $F$ by moving an unmatched endpoint with exchanges. If the first edge belongs to $I$, delete it first. For a graph cycle, delete one $I$-edge, move the unmatched endpoint around the opened cycle, then insert the last $F$-edge. Each intermediate state is a matching in a graph, and each entire transition path in a graph has length at most $4n$.

Fix a directed transition with initial state $M$. The complementary edge set $K=I△F△M$ agrees with one of the two matchings in a graph outside the active component and has at most two degree-two vertices on that component. Remove at most two offending edges to obtain a matching in a graph $K^{\prime }$. Store those edges and one bit specifying the initial alternating colour of the active component. This encoding is injective for the fixed transition: it restores $K$ and $I△F=M△K$, identifies the active component from the changed edges, and recovers the two colours using the fixed component order. Completed components have $F$'s colour in $M$, pending components have $I$'s colour, and the stored bit resolves the active component. Common edges are $M\cap K$.

There are at most $2(m+1{)}^2$ auxiliary records per $K^{\prime }$, where $m$ is the number of graph edges. If $d=|K|-|K^{\prime }|\le 2$, thenAlso $Q(M,M^{\prime })\ge {\pi }_{\lambda }(M)/(2m\max (\lambda ,{\lambda }^{-1}))$. Sum over the encodings and use the path length bound to obtainThis is polynomial whenever $\lambda$ and ${\lambda }^{-1}$ are polynomially bounded. Starting at the empty matching in a graph, $\log (1/{\pi }_{\lambda }(\varnothing ))=\log Z(\lambda )\le m\log (1+\lambda )$, so the Discrete Poincare inequality gives polynomial-time sampling to any prescribed total variation distance. The addition/deletion/exchange construction is also described in Section 12.4 of Jerrum and Sinclair's survey.

It remains to turn sampling into a relative count; merely sampling perfect matchings would not do that. For $0<\epsilon \le 1/2$, choose ${\lambda }_0=\epsilon /(8m)$ and ${\lambda }_{\ast }=8C_0/\epsilon$. The elementary bounds above giveChoose a schedule ${\lambda }_0<{\lambda }_1<\cdots <{\lambda }_J={\lambda }_{\ast }$ whose successive ratios are at most $1+1/n$. It has $J=O(n\log (n/\epsilon ))$ stages. The annealing ratios for a matching generating function satisfyEach observable lies in $[1,e]$, so the Hoeffding inequality gives relative accuracy $\eta =\epsilon /(10J)$ with $O({\eta }^{-2}\log (J/\delta ))$ independent samples per stage. Run independent copies of the chain from the empty matching in a graph; make the total variation distance per sample at most $\delta /(3JK)$, where $K$ is that sample count. The coupling characterization of total variation distance and the union bound make the entire sample collection coincide with exact stationary samples except with probability at most $\delta /3$. Choose the sample-count constant so all stationary sample means are accurate except with probability at most $\delta /3$.

Let $\hat{R}$ be the product of the sample means, and output $\hat{p}=\hat{R}/{\lambda }_{\ast }^n$. On the successful event its multiplicative error relative to $Z({\lambda }_{\ast })/Z({\lambda }_0)$ lies between $e^{-\epsilon /5}$ and $e^{\epsilon /5}$. Combining the two endpoint bounds provesActivities, sample counts, simulation lengths and rational bit lengths are polynomial in $n,{\epsilon }^{-1},\log ({\delta }^{-1})$. Thus this is a fully polynomial randomized approximation scheme. Small dimensions can be evaluated directly.

For disjoint vertex sets $A,B$, define their edge density of a bipartite graph by $d(A,B)=e(A,B)/(|A||B|)$. They form a regular pair with parameter $\epsilon$ if every $A^{\prime }\subseteq A,B^{\prime }\subseteq B$ with $|A^{\prime }|\ge \epsilon |A|$, $|B^{\prime }|\ge \epsilon |B|$ satisfies $|d(A^{\prime },B^{\prime })-d(A,B)|\le \epsilon$.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and minimum cell count $k_0$, some $K,n_0$ have the following property. Every graph on $n\ge n_0$ vertices admitswith $|V_0|\le \epsilon n$, equal-sized $V_1,\dots ,V_k$, and at most $\epsilon k^2$ unordered irregular pairs. It is enough to consider $0<\epsilon <1/2$.

Prove this using equitable regularity energy. Treat exceptional vertices as singleton cells and setwith ordered pairs and the adjacency indicator also defining diagonal densities. Then $0\le q\le 1$. The refinement variance identity for regularity energy proves refinement cannot decrease $q$:An irregular pair supplies witness subsets of relative sizes at least $\epsilon$ whose density differs by more than $\epsilon$. Refining along those witnesses raises $q$ by more than ${\epsilon }^4{L}^2/n^2$ per orientation, where $L$ is the common cell size. If there are more than $\epsilon k^2$ irregular pairs, the increase is greater than ${\epsilon }^5(kL/n{)}^2\ge {\epsilon }^5/4$, provided the exceptional set has size at most $n/2$.

Refine each cell by all its witness subsets; this produces at most $2^k$ atoms per cell. Restore equal sizes by the equalization with a controlled exceptional set: cut each atom into blocks of size $\lfloor L/4^k\rfloor$ and declare its remainder exceptional, still retaining every such vertex as a singleton in the energy. This is another refinement, so no energy is lost. At most $k{2}^k\lfloor L/4^k\rfloor \le n{2}^{-k}$ vertices become exceptional, and, when $L\ge 2\cdot 4^k$, at most $2k{4}^k$ new nonexceptional cells occur.

Put $T=\lceil 4{\epsilon }^{-5}\rceil$ and start with $k\ge k_0$ so large that $T{2}^{-k}\le \epsilon /2$. An initial equitable partition has at most $\epsilon n/2$ exceptional vertices when $n$ is sufficiently large. Subsequent cell counts only increase, so the total added exceptional set has size at most $\epsilon n/2$. The recurrence $k\mapsto 2k{4}^k$, iterated at most $T$ times, supplies a finite bound $K$; choose $n_0$ large enough that every intermediate $L$ meets the size requirement. More than $T$ unsuccessful refinements would raise $q$ above one. The process must therefore stop with the required regular pairs. This proves the lemma.

Its usefulness comes from replacing an arbitrarily large graph by the bounded reduced graph of a regularity partition. For fixed positive cross-density, the graph embedding lemma for regular pairs lifts fixed configurations from the reduced graph to the original one. In particular, three sufficiently regular positive-density pairs contain many triangles in a graph. Deleting exceptional, intracell, irregular and sparse-pair edges then gives the triangle removal lemma: a graph with sufficiently few triangles can be made triangle-free by deleting $o(n^2)$ edges. A triangle surviving in the reduced graph would force a positive proportion of the original possible triangles, a contradiction. More generally this approach yields the clique removal lemma and the asymptotic Erdős-Stone theorem. Applied to the tripartite graph encoding $x+z=2y$, triangle removal also gives Roth theorem on three-term arithmetic progressions. The price is that the energy argument gives a very rapidly growing, iterated-exponential bound on $K(\epsilon )$; the lemma is a structural tool, not a promise of small practical constants.

Let $t$ be the maximum number of positive Euclidean distances from one of the $n$ points to the others. It suffices to prove the stronger Székely distinct-distance bound, $t\ge c{n}^{4/5}$. Here $n\ge 2$; enlarge constants to handle bounded $n$.

First prove the crossing lemma for multigraphs. In an optimal drawing of a loopless multigraph with $v$ vertices, $e$ edges and maximum parallel multiplicity $\mu$, crossings of incident edges can be removed by interchanging initial segments, so each remaining crossing involves four distinct vertices. In each parallel class choose one of its edges with probability $1/\mu$ per edge, selecting none with the remaining probability. Independently keep each vertex with probability $p$. The resulting simple graph has expected edge count $p^{2}e/\mu$, expected vertex count $pv$, and expected crossings $p^{4}X/{\mu }^2$, where $X$ is the original crossing count. Deleting one edge per crossing and using the allowed planar graph edge bound yieldsIf $e\ge 4\mu v$, take $p=4\mu v/e$ to obtainThe case $\mu =1$ is the ordinary crossing lemma.

We also need the rich line bound. Given $L$ lines, connect consecutive incidence points on each line by straight edges. This simple graph has at least $I-L$ edges, where $I$ is the total number of incidences, and at most $L^2$ crossings. The crossing lemma gives $I=O((nL{)}^{2/3}+n+L)$, proving the Szemerédi–Trotter theorem here rather than assuming it. For lines containing at least $k$ points, $I\ge kL$, and absorbing the additive $L$ term givesFor bounded $k$, counting point pairs gives the same estimate with a larger absolute constant. Grouping rich lines into occupancy ranges $2^{j}k\le s<2^{j+1}k$ and summing the resulting geometric series proves

Now form the circular-arc graph for distinct distances. Around every point draw each positive-distance circle centred there; there are at most $nt$ such circles. A circle with at least three of the original points contributes one edge between each consecutive pair around it. Discard the circles with at most two points. Since the total number of centre-to-point incidences is $n(n-1)$, the remaining loopless multigraph hasIts circular-arc drawing has $O(n^2{t}^2)$ crossings: two distinct circles have at most two intersections, and small perturbations remove tangencies and multiple crossings without changing this order.

The apparent difficulty is unbounded parallel multiplicity. The rich-bisector deletion bound controls it. Every centre supporting an arc between fixed endpoints lies on their perpendicular bisector. Distinct parallel arcs come from distinct centres, since their common endpoints determine the radius once the centre is fixed. Thus multiplicity at least $k$ makes that line contain at least $k$ of the points. For a line with $s$ centres, each of its at most $st$ circles has at most two consecutive-point arcs symmetric about that line, one at each end of its diameter along the line. The occupancy sum above therefore bounds the number of high-multiplicity arcs by

If $t\ge n^{4/5}$ there is nothing to prove. Otherwise $t\log n=o(n)$ and $t=o(n)$. Choose $k=\lceil K\sqrt{t}\rceil$ with a sufficiently large absolute constant $K$. The first deletion term is at most a small fixed fraction of $n^2$ and the second is $o(n^2)$. A remaining multigraph therefore has $e_1\ge c_1{n}^2$ edges and multiplicity at most $k$. For large $n$, $e_1\ge 4kn$, so the crossing lemma for multigraphs givesRearranging,The whole distinct-distance set contains those distances from the selected point, proving the requested bound. The circular-arc method and the stronger one-point conclusion are due to Székely.

Let ${\mathrm{CLIQUE}}_{n,m}$ be the monotone Boolean function of the edge indicators asserting that an $n$-vertex graph contains an $m$-clique. We prove a superpolynomial monotone clique lower bound using a finite lattice of approximations. The only circuit theorem assumed is the Razborov gate-by-gate approximation lemma.

Fix integers $\ell ,r\ge 2$. Consider upward-closed set families $A$ of subsets of $[n]$ of size at most $\ell$. Impose the Razborov closure rule: if $W_1,\dots ,W_r\in A$ have pairwise intersections contained in $W$, adjoin $W$ whenever $|W|\le \ell$. Also normalize a family containing a set of size zero or one to the full family, since its clique predicate is identically true. Represent it byClosed families form the finite lattice approximation for monotone clique circuits, with meet $A\cap B$ and join $\mathrm{cl}(A\cup B)$. An input edge is represented by the family of its supersets up to size $\ell$. The constant predicates have the empty and full families. The assumed approximation theorem says that a size-$S$ circuit's output disagreement is covered by at most $S$ local gate errors:

We need the Erdős–Rado sunflower lemma: an $s$-uniform set family with more than $s!(r-1{)}^s$ members contains $r$ members with a common pairwise intersection. Its short induction proves the bound. A maximal disjoint subfamily either has $r$ members, already the required empty-core delta-system, or its union has at most $s(r-1)$ points and meets every member. Some point then occurs in more than $(s-1)!(r-1{)}^{s-1}$ members. Delete it, apply the induction hypothesis, and restore it to the core. Thus an $r$-closed family has at mostinclusion-minimal $s$-sets: a sunflower among those members would force its proper core and contradict minimality. This is the sunflower bound for minimal members of a Razborov-closed family.

For positive inputs choose a uniform $m$-subset $Z$ and the graph $K_Z$ having exactly the edges of its clique. Put $q=\ell rm/n$ and suppose $q\le 1/2$. A nonuniversal family has no minimal member of size at most one, so it accepts at mostof positive inputs. Here $\mathbb{P}(W\subseteq Z)=(m{)}_{|W|}/(n{)}_{|W|}\le (m/n{)}^{|W|}$.

If $K_Z$ is in a meet-error set, it contains minimal witnesses $X\in A,Y\in B$. Their union must have size greater than $\ell$, since otherwise upward closure would put it in $A\cap B$. At least one witness therefore has size greater than $\ell /2$. The same counting and the union bound give the positive clique error of a truncated lattice meet:

For negative inputs independently assign one of $m-1$ colours to each vertex, joining differently coloured vertices. Every resulting complete multipartite graph is $m$-clique-free. Consider one forcing step adjoining $W$. If its clique is newly accepted, $W$ is rainbow while all witnesses $W_i$ are not. Condition on the colours of $W$. The sets $W_i\setminus W$ are disjoint, so their non-rainbow events are conditionally independent. For each witness, every possible collision either involves two random petal colours or one petal colour and one fixed core colour; its probability is at mostWhen this is at most $1/2$, a step makes a negative error with probability at most $2^{-r}$. Upward closure itself introduces no extra accepted graphs, and normalization introduces no extra error beyond the forcing step that produced a set of size at most one. At most ${\sum }_{j=0}^{\ell }\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le n^{\ell +1}$ sets can be forced. The negative colouring error of a forced-set closure is therefore

Set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. For sufficiently large $n$, both probability conditions hold and $2q^2<1/2$. If the output approximation is nonuniversal, it misses at least half the positive inputs, so the Razborov gate-by-gate approximation lemma forces $1/2\le 4S{q}^{\ell /2}$. If it is universal, it accepts every negative colouring input, forcing $1\le S{n}^{\ell +1}{2}^{-r}$. ConsequentlySince $\log (1/q)\ge \frac{1}{2}\log n-\log \ell$ and $r$ grows faster than $(\log n{)}^2$, both terms implyfor an absolute positive $c$ and all sufficiently large $n$. This is superpolynomial in the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ input bits. The argument concerns AND/OR monotone circuits; it gives no such bound for circuits allowed negation.

The Frankl-Wilson theorem is a striking example of the polynomial method in combinatorics: an intersection restriction creates a family of linearly independent low-degree polynomials, whose dimension bounds the set family. Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s$ elements, and let $\mathcal{F}$ be a set family such that member sizes modulo $p$ avoid $L$ while every distinct pair has intersection size in $L$ modulo $p$. Its general modular form givesIf all members have the same size $k$ and $s\le k$, the uniform refinement gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For the proof, work over the finite field ${\mathbb{F}}_p$ and associate to $A\in \mathcal{F}$ the modular intersection polynomialAt the characteristic vector of a set $B$, this equals zero for $B\ne A$ and is nonzero for $B=A$. A linear relation among the evaluation functions therefore has every coefficient zero. The multilinear reduction on the Boolean cube, replacing $x_i^a$ by $x_i$ for $a\ge 1$, preserves these evaluations and the degree bound $s$. There are ${\sum }_{j=0}^s\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ possible square-free monomials, proving the general form.

For uniform members, the low-degree evaluation rank on a uniform layer supplies the sharper dimension bound. To verify this without division modulo $p$, form the integer incidence matrix with rows indexed by subsets $S$ of size at most $s$, columns indexed by $k$-subsets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, a row with $|S|=j$ is ${\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)}^{-1}$ times the sum of all size-$s$ rows containing $S$. Its matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is consequently zero and remains zero modulo $p$, giving the same bound over ${\mathbb{F}}_p$. The nonzero diagonal evaluation matrix of the $P_A$ then forces $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

The theorem, proved by Frankl and Wilson in 1981, extends the theme of the Ray-Chaudhuri–Wilson theorem from ordinary intersection sizes to residues. Modular restrictions can be weaker than exact intersection restrictions yet still force unexpectedly small families. Here are three consequences from one explicit modular intersection graph.

Take $N=4p-1$, $k=2p-1$, and let the vertices be all $k$-subsets of $[N]$, with an edge exactly when the intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so applying the Frankl-Wilson theorem with $L={\mathbb{F}}_p\setminus \{p-1\}$ givesA clique has one exact intersection size. Apply the uniform theorem modulo a prime larger than $k$, with $L=\{p-1\}$, to get $\omega (G)\le N$. Since there are $v=\left(\genfrac{}{}{0ex}{}{N}{k}\right)$ vertices, this gives the explicit asymmetric Ramsey number bound $R(N+1,B+1)>v$. It illustrates how algebraic constructions produce graphs with simultaneously restricted cliques and independent sets.

For a geometric application, map each vertex to $x_A=1_A/\sqrt{2p}$ in ${\mathbb{R}}^N$. Then $|x_A-x_B{|}^2=(k-|A\cap B|)/p$, so edges have unit Euclidean distance. Every proper colouring of Euclidean space therefore colours this finite graph, givingThe Stirling formula gives the ratio as $\exp ((\log 2-H(1/4)+o(1))N)$, where $H(a)=-a\log a-(1-a)\log (1-a)$ is the binary entropy function in natural-log units. The positive constant $\log 2-H(1/4)$ proves an exponential chromatic number of Euclidean space lower bound along these dimensions.

Finally, a quadratic embedding converts this same forbidden intersection into a forbidden diameter pair. Set $u_A=21_A-1$ and $Q_A=u_A{u}_A^T$. The quadratic sign-vector diameter formula follows from the Frobenius inner product:For distinct members the smallest possible absolute inner product is one, attained exactly when the intersection is $p-1$. Thus maximum-distance pairs are exactly edges of $G$. The matrices have common diagonal; using their off-diagonal coordinates, multiplied by $\sqrt{2}$, realizes them isometrically in $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ dimensions. They are distinct because equal outer products require $u_A=\pm u_B$, and complements have size $2p$, not $k$.

Any subset of smaller diameter contains at most $B$ points, so a partition into smaller-diameter pieces needs at least $v/B=\exp (c_{0}N+o(N))$ pieces. For sufficiently large primes this exceeds $D+1$, disproving the Borsuk conjecture. This is the mechanism behind the Kahn-Kalai counterexample to the Borsuk conjecture: the number of required pieces grows exponentially in the original set-system parameter while dimension grows quadratically. Their 1993 paper establishes the resulting high-dimensional counterexample.