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

Associate to each set $A_i\subseteq [n]$ its characteristic vector of a set $v_i\in {\mathbb{F}}_2^n$. The hypotheses sayIf ${\sum }_i{c}_i{v}_i=0$, taking the dot product with $v_j$ gives $c_j=0$. Thus the vectors are linearly independent, so $m\le \dim {\mathbb{F}}_2^n=n$. Equality is attained by the $n$ singleton sets.

Again let $v_i\in {\mathbb{F}}_2^n$ be the characteristic vectors. They all lie in the even-weight subspacewhich has dimension $n-1$. Their Gram matrix isbecause its diagonal entries are zero and its off-diagonal entries are one. If $Gx=0$ and $s={\sum }_i{x}_i$, then $x=s1$. ConsequentlySince $G=V{V}^T$ for a matrix whose rows lie in $E$, its rank is at most $n-1$. If $n$ is even, an even $m$ cannot reach $n$, while an odd $m$ is at most $n-1$; hence $m\le n-1$. If $n$ is odd, the same calculation gives $m\le n$.

Both bounds are sharp. For odd $n$, take $A_i=[n]\setminus \{i\}$ for $1\le i\le n$: each set has even size and two distinct sets meet in the odd number $n-2$. For even $n$, apply the same construction to $[n-1]$ and regard the resulting $n-1$ sets as subsets of $[n]$.

Let $k=k_1+\cdots +k_s$ be an integer partition. Partition $[2k]$ into blocks $X_j$ of sizes $2k_j$. For every $x\in X_j$, includeThere are $2k=n$ sets. Each has odd size; two sets from the same block meet in $2k_j-2$ points, and sets from different blocks are disjoint. Thus every pairwise intersection has even size.

The partition can be recovered from the bipartite incidence graph between the sets and ground points. A block with $k_j\ge 2$ gives one connected component containing $2k_j$ set-vertices and $2k_j$ point-vertices, while a block with $k_j=1$ gives two isolated edges. Therefore isomorphic families yield the same multiset $(k_1,\dots ,k_s)$. Distinct integer partitions give non-isomorphic families, so there are at least $p(k)$ of them.

We prove the Harris-Kleitman inequality by induction on $n$. For up-sets $\mathcal{A},\mathcal{B}\subseteq \mathcal{P}([n])$, let ${\mathcal{A}}_0,{\mathcal{A}}_1$ be their sections according as $n$ is absent or present, and write $a_i=|{\mathcal{A}}_i|$; define $b_i$ and $c_i=|{\mathcal{A}}_i\cap {\mathcal{B}}_i|$ similarly. Monotonicity gives $a_0\le a_1$ and $b_0\le b_1$. The induction hypothesis on $[n-1]$ givesIt remains only to observe thatHenceThe case $n=0$ starts the induction, so this is a proof from first principles.

Use the four families from the hint. Put $N=2^n$, $u=|{\mathcal{U}}_1|/N$, and $v=|{\mathcal{V}}_1|/N$. The families ${\mathcal{U}}_1,{\mathcal{V}}_1$ are up-sets, while their complements ${\mathcal{U}}_2,{\mathcal{V}}_2$ are down-sets. Applying the Harris-Kleitman inequality to the up-sets, and equivalently to the down-sets after taking complements of the ground set, givesThe cross-incomparability assumption givesConsequentlyThe Cauchy-Schwarz inequality now yieldsThis is the sharp two-family Cross-Sperner inequality.

Discard ground points lying in no set. For every point $x$ that lies in at least two members, formEvery pair of indices lies in exactly one $L_x$, and no $L_x$ equals $[n]$ because the total intersection is empty. Thus the $L_x$ form a finite linear space on the $n$ indices. The number of its lines through index $i$ is at most $a_i$, with equality unless $A_i$ contains private points.

The De Bruijn--Erdos pair-covering inequality says that if $r_i$ is the number of lines through point $i$ in a nontrivial finite linear space on $n$ points, thenApplying it here givesMoreover, a pair of ground points can lie in at most one $A_i$, since two different members meet in only one point. HenceCombining the inequalities gives $\left(\genfrac{}{}{0ex}{}{m}{2}\right)\ge \left(\genfrac{}{}{0ex}{}{n}{2}\right)$, and therefore $m\ge n$.

No example exists for $n=2$, because the unique point in $A_1\cap A_2$ would also lie in the total intersection; the one-member case is excluded by nontriviality. For every $n\ge 3$, take ground set $[n]$ and define the near-pencilTwo small sets meet in $n$, each small set meets $A_0$ in its other point, and the total intersection is empty. Thus the required values are exactly $n\ge 3$.

Yes. For every prime power $q\ge 2$, a finite projective plane of order $q$ haspoints and the same number of lines; every two lines meet in exactly one point, and the intersection of all lines is empty. Its lines therefore form one required family on $n$ points. The near-pencil from part (ii) is another. They are non-isomorphic because every projective-plane line has size $q+1$, whereas the near-pencil has a member of size $n-1$. There are infinitely many prime powers, so infinitely many such $n$.

Choose a Uniformly random maximal chain in a Boolean lattice. A fixed $h$-element set lies on the chain with probability ${\left(\genfrac{}{}{0ex}{}{n}{h}\right)}^{-1}$. Since an antichain meets any chain at most once, the expected number of its members on the chain is at most one:This is the Lubell--Yamamoto--Meshalkin inequality.

For the equality case, every maximal chain must meet $\mathcal{A}$. Suppose $S\in \mathcal{A}$ has size $h$ and $T$ is obtained from $S$ by exchanging one element. There is a maximal chain whose rank-$h$ member is $T$, whose rank-$(h-1)$ member is $S\cap T$, and whose rank-$(h+1)$ member is $S\cup T$. Every lower member is contained in $S$ and every higher member contains $S$, so antichainness excludes all of them. Equality forces $T\in \mathcal{A}$. The graph of $h$-subsets joined by one-element exchanges is connected, hence $\mathcal{A}=[n{]}^{(h)}$. Conversely, a full level clearly gives equality.

Since $\left(\genfrac{}{}{0ex}{}{n}{h}\right)\le \left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$,The equality characterization above leaves exactly either middle level. This proves Sperner theorem with its equality cases.

Fix $A\in \mathcal{F}$ and consider the tracesFor distinct $B,C\in \mathcal{F}\setminus \{A\}$, the hypothesis applied in both orders saysEquivalently, neither trace contains the other. Thus the traces are distinct and form an antichain in the Boolean lattice on the $2r$ points of $A$. By Sperner theorem,which is the required bound.