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

For $\mathcal{A}\subseteq [n{]}^{(r)}$, the Local LYM inequality isCount containment pairs $(B,A)$ with $B\in \partial \mathcal{A}$, $A\in \mathcal{A}$, and $B\subset A$. Every $A$ contributes $r$ pairs, while every $B$ contributes at most $n-r+1$. Hencewhich rearranges to the claimed normalized inequality.

The LYM inequality says that every antichain $\mathcal{F}\subseteq \mathcal{P}([n])$ satisfiesFor the local-LYM proof, replace the highest nonempty level of $\mathcal{F}$ by its lower shadow. No shadow member contains a surviving member, since that would make the original family non-antichain, and the local inequality says that the normalized size does not decrease. Repeating pushes the family to the bottom level, whose normalized size is at most one. Therefore the original normalized sum was at most one.

For the chain proof, choose a Uniformly random maximal chain in a Boolean lattice. A fixed $r$-set belongs to it with probability ${\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Since an antichain meets each chain at most once, the expected number of its members on the chain is at most one. Linearity of expectation gives the displayed sum.

Finally use a symmetric chain decomposition of a Boolean lattice. Convexity makes the intersection of $\mathcal{A}$ with each symmetric chain an interval. The alternating sum of $(-1{)}^{|A|}$ over an interval in a chain is $0$, $1$, or $-1$. There are exactly $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ chains, because each contains exactly one member of a middle level. Summing the chain contributions gives

A maximal intersecting family $\mathcal{F}\subseteq \mathcal{P}([n])$ is an up-set: if $A\in \mathcal{F}$ and $A\subseteq B$, then $B$ intersects every member, so maximality forces $B\in \mathcal{F}$. For every complementary pair $\{A,A^c\}$, at most one member lies in $\mathcal{F}$. If neither did, maximality would give $B\in \mathcal{F}$ disjoint from $A$; then $B\subseteq A^c$, and the up-set property would put $A^c$ in $\mathcal{F}$, a contradiction. Exactly one set from each complementary pair occurs, so

For $n\ge 4$, three pairwise nonisomorphic examples are:

Their smallest members have different sizes except at $n=4$, where the inclusion graphs of the minimal two-sets are respectively a triangle and a three-edge star. Thus they are nonisomorphic.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{F}\subseteq [n{]}^{(r)}$ is intersecting, thenFor the Kruskal-Katona theorem proof, the family of complements ${\mathcal{F}}^c\subseteq [n{]}^{(n-r)}$ is disjoint from the $(n-r)$th upper shadow of $\mathcal{F}$: otherwise one member of $\mathcal{F}$ would be contained in the complement of another. Kruskal–Katona says that when $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ this upper shadow has at least $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ members, with a strict corresponding inequality above that threshold. Since these two disjoint families lie in one level of size $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, the EKR bound follows.

For the averaging proof, place $[n]$ in a cyclic order. Among the $n$ cyclic intervals of length $r$, an intersecting family contains at most $r$: after fixing one interval, the possible intersecting intervals can be paired by their first separating endpoint. Double-counting pairs consisting of a cyclic order and a member of $\mathcal{F}$ that appears as an interval giveswhich is the same bound. This is the Katona circle method.

The minimum size $f_r(n)$ does not tend to infinity. Fix a core $S\subseteq [n]$ of size $2r-1$ and takeAny two members intersect. If an $r$-set $A$ is not contained in $S$, then $|A\cap S|\le r-1$, so the remaining at least $r$ points of $S$ contain a member of $\mathcal{F}$ disjoint from $A$. Thus $\mathcal{F}$ is maximal intersecting in $[n{]}^{(r)}$, andindependently of $n$.

Give $[k{]}^n$ its grid graph structure, with two points adjacent when they differ by one in one coordinate. The vertex-isoperimetric inequality in a grid states that among subsets of a given size, an initial segment of the simplicial order on a grid minimizes the external vertex boundary. The simplicial order first compares the coordinate sum and breaks ties by reverse lexicographic order.

To prove it, compress each coordinate fiber to an initial interval. Comparing the two endpoints of every fiber shows that a coordinate compression does not increase the external boundary. Repeating all coordinate compressions makes the family a down-set. Within each constant-sum layer, reverse-lexicographic compression again preserves size and cannot enlarge the boundary in either neighbouring layer. Induction on the dimension and on the layers then makes every section an initial segment compatible with the preceding section. The resulting family is exactly an initial simplicial segment, proving its extremality.

This is true. A simplicial initial segment in $[k{]}^2$ having both it and its complement larger than $(k^2-k)/2$ has an external vertex boundary of at least $k$. By the vertex-isoperimetric inequality, the same is true for every such $A$. If $A$ and $B$ were disjoint with no edge between them, then $B$ would avoid both $A$ and its external boundary, soThe hypotheses make the first two terms greater than $k^2-k$, contradicting $|{\partial }_{v}A|\ge k$.

This is false. For a central integer $s$, letThey are disjoint and no edge joins them; the omitted central layer has only $(3/4+o(1))k^2$ points. By choosing the central $s$ symmetrically, both sides havefor large $k$.

This is false. For arbitrarily large multiples $k$ of nine, take the vertical stripIt has $4k^2/9$ vertices, but only the $k$ horizontal edges crossing from column $4k/9$ to the next column leave it. Since $k<4k/3$, the proposed lower bound fails for infinitely many admissible $k$.

The Frankl-Wilson theorem says that if $p$ is prime, $L\subseteq {\mathbb{F}}_p$ has $s\le \min \{r,n-r\}$ elements, and $\mathcal{F}\subseteq [n{]}^{(r)}$ satisfiesthen $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

For each $A\in \mathcal{F}$, form the multilinearization on the Boolean cube ofAt the characteristic vector of a set $1_B$, this polynomial vanishes for $B\ne A$ and is nonzero for $B=A$. Hence the restricted functions $P_A$ are linearly independent. On the $r$-slice, every square-free monomial of degree below $s$ can be raised to degree $s$ using the relation ${\sum }_i{x}_i=r$, so the degree-at-most-$s$ function space is spanned by the $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$ square-free degree-$s$ monomials. Linear independence gives the theorem.

The answer is $\Theta (n^2)$. All four-sets containing one fixed pair form a family of sizewhose distinct intersections have size two or three. The Ray-Chaudhuri–Wilson theorem for the two allowed intersection sizes gives the matching $O(n^2)$ upper bound.

The answer is $\Theta (n)$. The familyhas size $n-3$ and pairwise intersection three. For the upper bound, work modulo two. Every member has size $0$ modulo two, while every allowed intersection has residue $1$. The Frankl-Wilson theorem with $L=\{1\}$ gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{1}\right)=n$.

The answer is $\Theta (n^2)$. Partition all but at most one point into $m=\lfloor n/2\rfloor$ disjoint pairs and take all unions of two pairs. There are $\left(\genfrac{}{}{0ex}{}{m}{2}\right)=\Theta (n^2)$ such four-sets, and two distinct unions intersect in zero or two points. The Ray-Chaudhuri–Wilson theorem gives the upper bound $O(n^2)$.

The answer is $\Theta (n^2)$. Take a Steiner triple system, or a partial one of quadratic size, on $\{2,\dots ,n\}$ and adjoin the fixed point $1$ to every triple. Distinct triples meet in zero or one point, so the resulting four-sets meet in one or two points. This gives $\Omega (n^2)$ members. The Ray-Chaudhuri–Wilson theorem with the two allowed intersection sizes gives $O(n^2)$.