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

Choose a Uniformly random maximal chain in a Boolean lattice by taking a uniformly random permutation of $X$ and successively adjoining its elements. A fixed $r$-element set occurs on this maximal chain in a Boolean lattice with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Because an antichain meets every such chain in a partially ordered set at most once, linearity of expectation gives the LYM inequality:Here $L(\mathcal{A})$ is the Lubell mass.

For equality in the LYM inequality, the integer $|\mathcal{A}\cap \mathcal{C}|\le 1$ must equal one for every maximal chain in a Boolean lattice, since every chain has positive probability. Choose $A\in \mathcal{A}$ of rank $r$. If $0<r<n$, take $x\in A$ and $y\notin A$, and choose a permutation with its first $r$ elements equal to $A$, its $r$th element $x$, and its next element $y$. Interchanging those two adjacent elements changes precisely the rank-$r$ member of the corresponding maximal chain in a Boolean lattice, replacing $A$ by $A^{\prime }=A\setminus \{x\}\cup \{y\}$. All other members are unchanged and none belongs to the antichain. The new chain must still meet $\mathcal{A}$, so $A^{\prime }\in \mathcal{A}$.

Successive exchanges connect all $r$-element subsets: exchange an element outside a desired target for an element missing from it, decreasing the number of differences each time. Thus $\mathcal{A}$ contains the whole rank-$r$ level. Every set of another rank is comparable with some set in that level, so the antichain contains nothing else. If $r=0$ or $r=n$, its sole possible member is already the whole corresponding level. Conversely, every full level meets every maximal chain in a Boolean lattice exactly once. Hence

A k-Sperner family meets every maximal chain in a Boolean lattice in at most $k$ members. The random-chain calculation in part (a) therefore gives the generalized LYM inequality $L(\mathcal{A})\le k$. Define the proportion of rank $i$ that is present byThen ${\sum }_i{x}_i=L(\mathcal{A})\le k$ and $w(\mathcal{A})={\sum }_{i}u(i)x_i$. This reduces the weighted theorem for k-Sperner families to allocating at most $k$ units of mass among ranks, each of capacity one.

To handle ties explicitly, let $t>0$ be the $k$th largest value among the $u(i)$, let $H=\{i:u(i)>t\}$, and put $h=|H|<k$. ThenThe last expression is exactly the sum of the $k$ largest rank weights, with multiplicity. Writing those values in descending order as $u_{(1)},\dots ,u_{(n+1)}$, the answer is

Choose $k$ distinct ranks whose $u(i)$ values are the $k$ largest, resolving any tie arbitrarily, and take the union of their full levels. Along a strict chain in a partially ordered set, cardinality strictly increases, so this set family is a k-Sperner family. Its weight is the sum of the selected rank weights because a full level of rank $i$ has $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ members. Thus the bound in the weighted theorem for k-Sperner families is always attained:

First we need all equality cases, rather than just the examples from part (c). The threshold estimate in part (b), with $t>0$, shows that any maximum-weight k-Sperner family has Lubell mass exactly $k$.

For each $A\in \mathcal{A}$, let $\ell (A)$ be the largest number of members in a strict chain in a partially ordered set within $\mathcal{A}$ ending at $A$. Its values lie in $\{1,\dots ,k\}$. If $A⊊B$ then $\ell (B)\ge \ell (A)+1$, so each height class ${\mathcal{A}}_j=\{A:\ell (A)=j\}$ is an antichain. Its Lubell mass is at most one by the LYM inequality, andConsequently every height class has Lubell mass one. By equality in the LYM inequality, each is a full rank level. Since the classes are disjoint, the maximizing family is a union of exactly $k$ distinct full levels.

Let $t$ again be the $k$th largest $u(i)$, let $h$ ranks have $u(i)>t$, and let $s$ ranks have $u(i)=t$. Equality in the threshold estimate requires all $h$ higher-weight levels, no lower-weight levels, and any $k-h$ of the $s$ tied levels. Thus the number of maximizing weighted k-Sperner families isConversely, every such $h,s$ is realizable. Assign $u(i)=2$ on $h$ chosen ranks, $u(i)=1$ on $s$ further ranks, and $u(i)=1/2$ on all remaining ranks, then set $w(i)=u(i)/\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. These weights are positive and have exactly the stated tie pattern.

Putting $j=k-h$ gives a concise classification of the possible integers:Repeated values in this set are counted only once. The possible counts need not form an interval: for example, when $n=5,k=2$ they are $1,2,3,4,5,6,10,15$.

Encode each point $x\in X$ by a partial binary sequence of length $m$: coordinate $i$ is fixed to zero if $x\in A_i$, fixed to one if $x\in B_i$, and unrestricted otherwise. Disjointness makes these prescriptions consistent. Let $d(x)$ be the number of fixed coordinates, equivalently the number of pairs containing $x$, and let $S_x\subseteq \{0,1{\}}^m$ be the set of complete sequences consistent with them. Then $|S_x|=2^{m-d(x)}$.

The separating family of disjoint set pairs ensures that $S_x$ and $S_y$ are disjoint whenever $x\ne y$: one coordinate prescribes opposite bits. Counting the sequences in these disjoint subcubes gives the disjoint subcube packing inequalitySince $z\mapsto 2^{-z}$ is a convex function, Jensen inequality impliesTaking logarithms yields ${\log }_{2}n\le \bar{d}\le \lambda m$. Therefore, for $\lambda >0$,The PDF omits the qualification $\lambda >0$. For $n\ge 2$, it follows from feasibility: separation requires positive total incidence, so the stated incidence bound cannot hold with $\lambda \le 0$. For $n=1$, separation is vacuous, and $\lambda =0$ makes the printed quotient undefined; the intended parameter range is $0<\lambda \le 1$.

Put $m=\lceil {\log }_{2}n\rceil$ and assign distinct complete binary sequences in $\{0,1{\}}^m$ to the $n$ points. For each coordinate $i$, let $A_i$ be the points with bit zero and $B_i$ those with bit one. Distinct sequences disagree in some coordinate, so these pairs form a separating family of disjoint set pairs.

Every point lies in exactly one side of every pair, hence the total incidence is $mn$, as allowed when $\lambda =1$. The construction reaches the bound:The reference to “(i)” in the original PDF's part (b) refers to part (a); the local TeX additionally duplicates that item.

For $n=4$, the lower bound is four pairs. On $X=\{1,2,3,4\}$ useThe first pair separates points in different halves, and the next two separate points within each half. The four pairs are distinct and have total incidence $4+2+2+0=8=(1/2)\cdot 4\cdot 4$. They are therefore a valid separating family of disjoint set pairs attaining the bound.

For $n=8$, label points by triples $(u,v,w)\in \{0,1{\}}^3$. The following six pairs attain the bound of six. Coordinates not mentioned in a row are unrestricted:If two triples first differ in $u$, row 1 separates them. If they agree in $u$ and differ in $v$, row 2 or 3 does. If they agree in both and differ in $w$, row 4, 5, or 6 does. The total incidence is $24=(1/2)\cdot 6\cdot 8$, and each point belongs to exactly three pairs. ThusThe empty fourth pair matters for $n=4$. The original PDF requires disjoint subsets but does not require either side to be nonempty, so the construction is permitted. Under the additional convention that both sides of every pair must be nonempty, the $n=4$ answer would be no: four pairs of total incidence at most eight would each have two singleton sides and could separate at most four of the six unordered pairs of points. The $n=8$ construction already has both sides nonempty.

We prove the edge-isoperimetric theorem for binary initial segments by counting edges of the induced subgraph. Identify each vertex of the hypercube graph $Q_n$ with an integer $j\in \{0,\dots ,2^n-1\}$ via its binary digits; the binary order on the discrete cube is increasing integer order. Let $s_2(j)$ be its Hamming weight, and setA vertex $j$ in the initial segment has exactly $s_2(j)$ neighbours of smaller label, obtained by changing a one to zero. Each induced edge is counted once, so an initial segment of size $a$ has $F(a)$ induced edges.

The arithmetic ingredient is the binary digit-sum inequalityHere is a proof, including the parity cases needed for arbitrary sizes. Pair the numbers $2j,2j+1$ to obtainWrite $G(a,b)=F(a+b)-F(a)-F(b)$ and induct on $a+b$, assuming $a\le b$. If $a=0$, the claim is immediate. Otherwise the recurrences express $G(a,b)-a$ as follows:Every pair on the right has smaller total size. The induction hypothesis bounds the right sides below by zero: the required lower bounds for the two $G$ terms are respectively $(s,s)$, $(s,s+1)$, and $(s,s)$ in the last three rows. This establishes the binary digit-sum inequality.

Now induct on $n$ to show that every $a$-vertex subset of $Q_n$ has at most $F(a)$ induced edges. The zero-dimensional case is immediate. Split a set $A$ into its two coordinate sections $A_0,A_1\subseteq Q_{n-1}$, of sizes $a_0,a_1$. By induction the edges within the sections number at most $F(a_0)+F(a_1)$. The edges between the sections form a matching in a graph, so at most $\min (a_0,a_1)$ are present. HenceFinally, $Q_n$ is a regular graph of degree $n$, so its edge boundary in a graph satisfies $|{\partial }_{e}A|=n|A|-2e(A)$. For the binary initial segment $C$, equality $e(C)=F(|A|)$ holds. Therefore

We establish small-set edge isoperimetry in a square grid directly by counting row and column transitions. Regard the vertices of the grid graph as $[n]\times [n]$. Put $s=a-(b-1{)}^2$, so $1\le s\le b-1$. Start with the corner square $[b-1]\times [b-1]$ and add the $s$ vertices $(1,b),\dots ,(s,b)$. In this shape every occupied row and column is a proper initial interval. There are $b-1$ occupied rows and $b$ occupied columns, each contributing exactly one edge to the edge boundary in a graph in its direction. This gives $f_n(a)\le 2b-1$.

For the reverse bound take an arbitrary $a$-vertex set $A$, and let $R,C$ be its numbers of occupied rows and columns. A row or column that is occupied but not full has at least one transition between $A$ and its complement, hence at least one corresponding boundary edge.

Suppose first that no row and no column is full. Then $|{\partial }_{e}A|\ge R+C$ and $a\le RC$. If $R+C\le 2b-2$, the arithmetic-geometric mean inequality would givecontrary to the stipulated size. Thus $|{\partial }_{e}A|\ge 2b-1$.

If there is a full row but no full column, all $n$ columns are occupied and proper, giving at least $n>2b-1$ vertical boundary edges. The case of a full column but no full row is identical with the directions exchanged.

It remains to consider a set with both a full row and a full column. All rows and columns are now occupied. If $q$ rows and $t$ columns are full, then $qn\le a$ and $tn\le a$. The remaining rows and columns each contribute a boundary edge, soSince $a\le b^2-b<b^2<n^2/4$, this exceeds $3n/2$, which is larger than $2b-1$. These cases exhaust all sets and proveAs usual, $a$ and $b$ are integers; the specified interval is nonempty only for $b\ge 2$.

Let $D_n(a)$ denote the constant term, retaining the dimension as a subscript when it changes. We use the Good recurrence for the Dyson constant term. For algebraically independent variables, Lagrange interpolation polynomial applied to the constant polynomial one givesAt $t=0$, this becomes the rational identityWhen every $a_i>0$, multiplying by the given Laurent polynomial cancels one factor in row $i$ of the product and givesThis is a polynomial identity after cancellation; no choice of an expansion of a rational function is involved.

The boundary case is essential. If $a_i=0$, the factors in row $i$ are absent. The only factors involving $X_i$ are then $(1-X_j/X_i{)}^{a_j}$ for $j\ne i$, and all their powers of $X_i$ are nonpositive. To obtain power zero in $X_i$, one must select the constant term one from each of them. Taking the constant term in $X_i$ therefore deletes that variable and exponent:For $n=1$, the empty product is one, so $D_1(a_1)=1$. The all-zero exponent vector also gives one.

Now put $M_n(a)=m!/{\prod }_i{a}_i!$, where $m={\sum }_i{a}_i$. This multinomial coefficient obeys the same deletion rule for a zero exponent. For positive exponents,Induction on $n$, and within each dimension on $m$, consequently determines $D_n$ uniquely and identifies it with $M_n$. This proves the Dyson constant-term identity:

Work in the prime field ${\mathbb{F}}_p$ and set $r=p-1$. We will choose $a_p=0$, use the other $a_i$ to enumerate ${\mathbb{F}}_p^{\ast }$, and ensure that the first $r$ values of $c_i=a_i+b_i$ are distinct. The zero-sum condition will then force the last value to be the missing field element.

Consider the polynomialIt has total degree of a polynomial $r(r-1)$. Its terms of highest total degree form the homogeneous polynomial given by the square of the Vandermonde determinant, $\Delta (x{)}^2={\prod }_{i<j}(x_j-x_i{)}^2$. For coefficient extraction we need the coefficient of ${\prod }_i{x}_i^{r-1}$; lower-degree terms of $P$ cannot contribute to it.

Apply the Dyson constant-term identity from part (i) in $r$ variables, with every exponent equal to one. Pairing its factors for $i,j$ givesThe constant term is $r!$. Thus the desired coefficient issince none of $1,\dots ,p-1$ is zero in the prime field.

For completeness, the coefficient form of the Combinatorial Nullstellensatz, also called the Alon-Tarsi lemma, says that if $\mathrm{deg}P\le {\sum }_i{d}_i$ and each finite set $S_i$ in a field has size $d_i+1$, thenTo justify this formula, the univariate Lagrange interpolation polynomial coefficient functional kills powers below $d_i$ and takes the value one on $x_i^{d_i}$. Apply the product of these functionals to each monomial of $P$. Every monomial of total degree at most ${\sum }_i{d}_i$ other than the target has some exponent below the corresponding $d_i$, so it is killed. The target survives with coefficient one. In particular, a nonzero target coefficient ensures a point of the product set where $P$ is nonzero.

Use $S_i={\mathbb{F}}_p^{\ast }$ and $d_i=r-1$ for every $i$. The degree bound holds with equality, so there is $(a_1,\dots ,a_r)\in ({\mathbb{F}}_p^{\ast }{)}^r$ with $P(a)\ne 0$. Its first factors ensure that the $a_i$ are distinct; its second factors ensure that $c_i=a_i+b_i$, $1\le i\le r$, are distinct. With $a_p=0$, the $a_i$ enumerate the whole prime field.

Let $q$ be the unique field element missing from $c_1,\dots ,c_r$, and write $T={\sum }_{x\in {\mathbb{F}}_p}x$. Since ${\sum }_i{b}_i=0$,The same sum is $T-q$, hence $q=b_p$. Taking $c_p=b_p=a_p+b_p$ completes the enumeration. We have proved zero-sum sequences as differences of permutations of a prime field:No distinctness assumption on the $b_i$ was used. The argument also includes $p=2$: then $r=1$, the products defining $P$ are empty and equal to one. Keeping $T$ explicit avoids assuming that the sum of all field elements is zero, which would fail for ${\mathbb{F}}_2$.