Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 13 (Extremal Combinatorics)

Put $m=p^a$, with $p$ a prime number, and $s=m-1$. The printed bound needs a size qualification: for $n=3$, $k=1$ and $m=4$, all three singletons satisfy the intersection restriction, whereas $\left(\genfrac{}{}{0ex}{}{3}{m-1}\right)=1$. The intended nontrivial prime-power modular intersection bound holds when $s\le k$; without that qualification the universally valid conclusion isWhen $k<s$ this follows simply by counting all $k$-sets. We prove the sharper intended form for $s\le k$.

Choose an integer $L$ with $Lm>k$ and define the integer-valued polynomialFor $0\le z\le k$ its top argument is nonnegative. The bottom argument has all its first $a$ base-$p$ digits equal to $p-1$. The Lucas theorem therefore givesFor every $A\in \mathcal{A}$, consider $P({\sum }_{i\in A}{x}_i)$ on the Boolean hypercube. Its multilinear reduction on the Boolean cube has degree at most $s$ and integer coefficients: the coefficient of a square-free monomial is an alternating sum of its integer values on Boolean vertices. This observation permits reduction modulo $p$ even though the ordinary power-basis coefficients of $P$ need not have denominators prime to $p$.

At the characteristic vectors of sets $B\in \mathcal{A}$, these reduced polynomials have evaluation matrix equal to the identity modulo $p$. Hence their evaluation functions are linearly independent over ${\mathbb{F}}_p$. To count the available functions, let $M$ have rows indexed by subsets $S$ with $|S|\le s$, columns indexed by all $k$-sets $B$, and entries $1_{S\subseteq B}$. Over the rational numbers, for $|S|=j$,Thus the matrix rank over the rational numbers is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger integer minor is zero and remains zero modulo $p$, so the same rank bound holds over ${\mathbb{F}}_p$. This low-degree evaluation rank on a uniform layer proves

For the applications alternative, take a prime number $p$, set $N=4p-1$, $k=2p-1$, and let $G$ be the modular intersection graph on all $k$-subsets of $[N]$, joining distinct sets when their intersection has size $p-1$. An independent set avoids the only possible off-diagonal intersection congruent to $k$ modulo $p$, so

First embed $A$ as $v_A=1_A/\sqrt{2p}$ in Euclidean space. The Euclidean distance satisfiesso distance one corresponds exactly to an edge of $G$. Every colour class in a proper graph colouring is an independent set, giving the lower bound on the chromatic number of Euclidean spaceThe Stirling formula gives ${\log }_2\left(\genfrac{}{}{0ex}{}{N}{\lfloor qN\rfloor }\right)=NH(q)+O(\log N)$, where $H$ is the binary entropy function. Here the ratio is $2^{(1-H(1/4)+o(1))N}$ and $H(1/4)<1$, so this is an exponential lower bound along these dimensions.

Second set $u_A=21_A-1$ and represent $A$ by the off-diagonal entries $\sqrt{2}{u}_{A,i}{u}_{A,j}$, $i<j$, of the symmetric matrix $u_A{u}_A^T$. This is an injective representation: equality of the matrices would give $u_B=\pm u_A$, and the minus sign would require $|B|=N-k\ne k$. The common diagonal can be omitted without changing distances. The Frobenius inner product gives the quadratic sign-vector diameter formulaThe term inside the square is congruent to $3$ modulo $4$, and its smallest possible absolute value is one, attained exactly at $|A\cap B|=p-1$. Such pairs exist. Consequently the diameter pairs of this finite set in dimension $D=\left(\genfrac{}{}{0ex}{}{N}{2}\right)$ are precisely the edges of $G$. Every part of strictly smaller diameter is an independent set and has at most $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$ points. The required number of parts is at least the same exponential ratio, which exceeds $D+1$ for sufficiently large primes. Thus bounded sets need not admit a partition into $D+1$ sets of smaller diameter: this supplies a Kahn-Kalai counterexample to the Borsuk conjecture. Both applications use the prime case of the proved prime-power result.

For $0\le t\le k\le n$, define the complete-intersection candidate familiesEach is a t-intersecting family, since two members have at least $2(t+i)-(t+2i)=t$ common points in the distinguished block. The cardinality form of the Ahlswede-Khachatrian theorem isA binomial coefficient with lower argument outside its usual range is zero. For $t=0$, or $n\le 2k-t$, the answer is $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; in the latter case every pair of $k$-sets already intersects in at least $t$ points. The displayed candidate formula also attains this value: its largest allowed index is at least $n-k$, so every $k$-set has enough points in that candidate's block. For $t=k$ the answer is one. We prove the remaining cases without assuming the complete intersection theorem as an auxiliary result.

We first record the $t=1$ case of the Erdős-Ko-Rado theorem. For $n\ge 2k$, put the ground set in a cyclic ordering. An intersecting family contains at most $k$ of its length-$k$ intervals. To see this, rotate a selected interval to end at position $n$. Intervals ending at $k,\dots ,n-k$ miss it. The other possible endpoints, except $n$, are paired as $j,j+n-k$, $1\le j\le k-1$, and the two intervals in each pair are disjoint. Thus at most $1+(k-1)=k$ intervals are selected. Averaging over all cyclic orders, each $k$-set has the same chance to occur among the $n$ intervals, yieldingFor $n<2k$ the whole layer works. This proves the $t=1$ case, including $n=2k$ without any uniqueness assertion.

We may now suppose $2\le t<k$ and $n>2k-t$. If $n=2k-t+1$, complementation of uniform intersecting families changes the problem to an intersecting family of $(k-t+1)$-sets. The just-proved case gives $M(n,k,t)=\left(\genfrac{}{}{0ex}{}{n-1}{k-t}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. This is $|{\mathcal{F}}_{k-t}|$, the family of all $k$-sets avoiding the last coordinate. Hence it remains to treat $n\ge 2k-t+2$.

Apply coordinate shifts of a set family with $i<j$. They preserve cardinality and t-intersection. The only way a moved member could lose an intersection point with an unmoved member is that the former moves $j$ to $i$ while the latter contains $j$ and avoids $i$. The latter's shifted partner must already belong to the original family, since otherwise it too would move; that partner would have had an intersection of size less than $t$ with the original moved member, a contradiction. If both members move, their intersection size is unchanged. Every nontrivial shift decreases the sum of all coordinates in all members, so repeated shifts terminate at a left-compressed set family. We can therefore choose a maximum family $\mathcal{A}$ left-compressed.

We prove the small-support generating lemma for extremal intersecting families, including the replacement argument responsible for the threshold. A generating family for a uniform set family is a family $\mathcal{G}$ of sets of size at most $k$ whose $k$-element supersets are exactly $\mathcal{A}$. Start with $\mathcal{G}=\mathcal{A}$. A left shift of a generator still has every $k$-element extension in $\mathcal{A}$: if the extension contains the removed coordinate it already contains the old generator; otherwise reverse that shift in the extension and use left-compression of $\mathcal{A}$. Taking all left shifts of generators, then deleting inclusion-redundant generators, therefore gives an antichain of generators with the following property: every left shift of a generator contains a generator. This normalization never enlarges the support. Choose a normalized generating family whose largest support coordinate $m$ is as small as possible.

The generators themselves are t-intersecting. Indeed, if two generators intersect in fewer than $t$ points, they can be extended to $k$-sets with intersection size $\max \{|G\cap H|,2k-n\}<t$: fill their two residual quotas with disjoint points as far as possible. This contradicts the defining property of the generated family. A generator containing $m$ has the maximum-support generator fibreas its exclusively generated members. In fact, any extra coordinate $i<m$ in the prefix supplies a generator inside $G-\{m\}+\{i\}$, which avoids $m$ and also generates that member. An exact prefix $G$ contains no other generator by the antichain property.

If two generators containing $m$ have intersection exactly $t$, they must have union $[m]$: any earlier coordinate missing from both permits shifting $m$ out of one generator and lowers their intersection below $t$. Thus tight pairs of left-compressed generators have sizes summing to $m+t$. Write ${\mathcal{G}}_a$ for the generators of size $a$ containing $m$, and put $N=n-m$. Generators avoiding $m$ still meet a shortened generator in at least $t$ points, and shortened generators in classes $a,b$ still meet in at least $t$ unless $a+b=m+t$.

SupposeWe will contradict extremality or the minimality of $m$. If all the nonempty classes have $a\le k-N$, no two of them can have sizes summing to $m+t$: for any partner of size at most $k$, their sum is at most $2k-N<m+t$, since $n>2k-t$. We may therefore shorten every generator containing $m$, preserving t-intersection and generating a family containing $\mathcal{A}$. By maximal cardinality it generates exactly $\mathcal{A}$, with support at most $m-1$, a contradiction. There must be a class with $a>k-N$.

If such a class has $2a\ne m+t$, put $b=m+t-a$. Remove classes $a,b$ and insert all shortened generators from class $a$, or instead all shortened generators from class $b$. Both replacements remain t-intersecting. The first loses exactly $|{\mathcal{G}}_b|\left(\genfrac{}{}{0ex}{}{N}{k-b}\right)$ exclusively generated members and gains at least $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a+1}\right)$ new members with shortened exact prefixes and tails beyond $m$; the second gives the reversed comparison. If class $b$ is empty, the first gain is positive and contradicts extremality. Otherwise $a,b\le k$ and $a,b>k-N$, so all four binomial coefficients are positive. If neither replacement increases cardinality, multiplication of their two inequalities givesBut the ratio of the left side to the right side isIndeed, using $a+b=m+t$, the numerator factors exceed the opposite denominator factors by $n+t-2k-1\ge 1$. This contradiction excludes every noncentral class with positive fibre.

Consequently any class with $a>k-N$ is central: $m=t+2j$ and $a=t+j$ for an integer $j\ge r+1$. Shorten the central generators. Each shortened set misses exactly $j$ of the $m-1$ earlier coordinates, so some coordinate $h<m$ is absent from at least $j|{\mathcal{G}}_a|/(m-1)$ of them. Call that subfamily $\mathcal{T}$. Its members are t-intersecting: a bad pair would have arisen from a tight pair whose union was $[m]$, whereas both shortened sets avoid $h$. They also meet all unchanged generators in at least $t$ points; a conflicting class would have to be the central class itself. Remove the entire central class and insert $\mathcal{T}$. The loss relative to the unaffected generators is exactly $|{\mathcal{G}}_a|\left(\genfrac{}{}{0ex}{}{N}{k-a}\right)$. Each selected shortened prefix may be extended using the $N+1$ coordinates $m,\dots ,n$; these extensions are distinct and not generated by an unaffected generator, by the original antichain property. The number restored or added is at least $|\mathcal{T}|\left(\genfrac{}{}{0ex}{}{N+1}{k-a+1}\right)$. Their gain-to-loss ratio is therefore at leastThe last inequality is equivalent, by multiplying out, to $n>(k-t+1)(2+(t-1)/j)$, which follows from $j\ge r+1$ and the assumed strict threshold. This finishes the generator replacement proof of the small-support intersection lemma:Reflection gives the analogous supporting suffix for a right-compressed optimum.

The second ingredient is the compatibility bound for complementary generating families. Let $\mathcal{H}$ generate ${\mathcal{A}}^c=\{[n]\setminus A:A\in \mathcal{A}\}$, a $(n-2k+t)$-intersecting family of $(n-k)$-sets. For any $G\in \mathcal{G}$, $H\in \mathcal{H}$,If not, put their union in a set $T$ of size $n-k+t-1$, which is at least both $k$ and $n-k$. Extend $G$ within $T$ to a $k$-set $A\in \mathcal{A}$ and $H$ within $T$ to an $(n-k)$-set $B\in {\mathcal{A}}^c$. Then $B^c\in \mathcal{A}$, but $|A\cap B^c|=|A\cup B|-|B|\le t-1$, a contradiction.

SetFirst suppose $n_{r+1}<n<n_r$. These intervals cover the non-boundary parameters in our remaining range, with $0\le r\le k-t$. The support lemma gives generators on the prefix $[t+2r]$. Write $k^{\prime }=n-k$, $t^{\prime }=n-2k+t$ and $r^{\prime }=k-t-r$. Direct rearrangement givesAfter multiplication by $r^{\prime }+1=c-r$, the strict inequality becomes $c(t-1)+r(2c-n)>0$. For $r>0$ this is exactly $n<n_r$; for $r=0$ it is $c(t-1)>0$. Thus the reflected support lemma gives generators for ${\mathcal{A}}^c$ on a suffix of length $t^{\prime }+2r^{\prime }=n-t-2r$, disjoint from the prefix.

If every prefix generator has size at least $t+r$, then $\mathcal{A}\subseteq {\mathcal{F}}_r$. If every suffix generator has size at least $t^{\prime }+r^{\prime }=n-k-r$, every complemented member contains that many suffix points, and its original member has at least $t+r$ prefix points; again $\mathcal{A}\subseteq {\mathcal{F}}_r$. At least one of these alternatives holds: otherwise generators of sizes at most $t+r-1$ and $n-k-r-1$ would have union of size at most $n-k+t-2$, violating compatibility. Since ${\mathcal{F}}_r$ itself is t-intersecting and $\mathcal{A}$ is maximum,

Finally suppose $n=n_{r+1}>2k-t+1$. The support lemma, now with index $r+1$, places $\mathcal{G}$ in $[t+2r+2]$. For the complement, the strict support inequality still places $\mathcal{H}$ in the suffix beginning at $t+2r+1$. These supports overlap in two coordinates, which is harmless for the union bound in compatibility. Either every $G$ has size at least $t+r+1$, placing $\mathcal{A}$ inside ${\mathcal{F}}_{r+1}$, or every $H$ has size at least $n-k-r$, placing $\mathcal{A}$ inside ${\mathcal{F}}_r$. If neither held, a pair of generators would have union of size at most $n-k+t-1$, again impossible.

The two candidate sizes agree at this boundary. In passing from ${\mathcal{F}}_r$ to ${\mathcal{F}}_{r+1}$, the gained sets have $t+r-1$ points in the old block and both new points; the lost sets have $t+r$ old-block points and neither new point. Their counts areThe ratio is one exactly when $(r+1)n=c(t+2r+1)$, that is, $n=n_{r+1}$. Therefore $M=|{\mathcal{F}}_r|=|{\mathcal{F}}_{r+1}|$ there. The full-level cases, the elementary $t=1$ proof, the complementary borderline case, and these strict-interval and boundary arguments establish the boxed cardinality theorem for every admissible parameter.

Write $a_n=|{\mathcal{P}}_n|$ for the number of labelled $r$-uniform hypergraphs with the hereditary hypergraph property, so $d_n=a_n^{1/\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$ for $n\ge r$. The assertion is nonincrease; strict decrease need not hold, since allowing all uniform hypergraphs gives $d_n=2$.

If $a_n=0$, heredity forces $a_{n+1}=0$. If $a_{n+1}=0$, the desired inequality is immediate. Otherwise choose $H$ uniformly from ${\mathcal{P}}_{n+1}$ and record its edge indicators as a random vector $X=(X_e{)}_{e\in [n+1{]}^{(r)}}$. Its information entropy, with any fixed logarithm base, is $H(X)=\log a_{n+1}$. Deleting a vertex $v$ gives the restriction $X^{(v)}$ to the edges avoiding $v$. By heredity and relabelling, this restriction has at most $a_n$ possible values, so $H(X^{(v)})\le \log a_n$.

Each edge coordinate occurs in exactly $n+1-r$ of these restrictions. For completeness, order all the edge coordinates. The chain rule for information entropy expands a restriction entropy as a sum of conditional coordinate entropies. The predecessors retained in a restriction form a subset of all predecessors, and conditioning reduces entropy; hence each restriction term is at least the corresponding full-vector term. Summing over the restrictions counts each full-vector term $n+1-r$ times. This proves the needed Shearer inequality:Since $\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)=\frac{n+1}{n+1-r}\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, division gives $\log d_{n+1}\le \log d_n$. Therefore the normalized speed of a hereditary hypergraph property satisfies

Let $H$ be the $r$-uniform hypergraph and use strong saturation of a uniform hypergraph in its immediate-completion sense: each missing edge $e$ lies in an $(r+t)$-set $T$ whose other $r$-subsets are already edges of $H$. The argument allows existing hypergraph cliques. Take $n\ge r+t$, the usual parameter range; if $r\le n<r+t$, strong saturation forces every possible edge to be present, and the inequality is immediate whenever its binomial terms are defined. The case $t=0$ has the trivial lower bound zero.

For $t\ge 1$, choose distinct real numbers $z_1,\dots ,z_n$ and form the $t\times n$ Vandermonde matrix $M$ whose $i$th column is $(1,z_i,\dots ,z_i^{t-1}{)}^T$. Every $t$ columns are linearly independent by the Vandermonde determinant. Set $U=\ker M\subseteq {\mathbb{R}}^n$, so $\dim U=n-t$, and work in the quotient vector spaceHere the inclusion of ${\bigwedge }^{r}U$ is injective: extend a basis of $U$ to a basis of ${\mathbb{R}}^n$ and use the resulting wedge bases of the exterior powers. Write $w_e$ for the image in $W$ of the coordinate wedge indexed by an $r$-set $e$. All these images span $W$.

For any $(r+t)$-set $T$, let $V_T$ be its coordinate subspace. The restriction of $M$ has rank $t$, so $U\cap V_T$ has dimension $r$. Wedge a basis of this intersection to obtain a nonzero elementEvery coefficient $c_e$ is nonzero. Indeed, projection of $U\cap V_T$ onto the $e$ coordinates is an isomorphism: a vector in its kernel is supported on $T\setminus e$, whose $t$ columns of $M$ are independent. The coefficient is the determinant of that projection in the chosen bases. Passing to $W$ therefore gives a linear dependence

If $e$ is missing from $H$, take its strong-saturation witness $T$. The dependence expresses $w_e$ in the span of the $w_f$ for the other edges $f\subseteq T$, all of which are present. Thus the vectors indexed by the present edges span all of $W$. The exterior-power quotient bound for strong hypergraph saturation follows:The bound is sharp: include precisely the $r$-sets meeting one fixed $t$-set $S$. A missing edge $e$ is disjoint from $S$, and every other $r$-subset of $e\cup S$ meets $S$, so adding $e$ immediately completes a hypergraph clique of order $r+t$. The number of included edges is exactly the displayed bound.

Identify the vertices of the Boolean hypercube with subsets of $[n]$. Write $N(\mathcal{A})$ for the closed vertex neighbourhood and $\partial \mathcal{A}=N(\mathcal{A})\setminus \mathcal{A}$ for the external vertex boundary. The cube order used here is the simplicial order on the discrete cube: increasing size, then lexicographic order, with the smallest differing coordinate belonging to the earlier set. We prove Harper theorem by induction on $n$; subtracting the common size of the families converts a closed-neighbourhood comparison into the required boundary comparison.

First, the closed neighbourhood of a simplicial initial segment is itself an initial segment. Such a family consists of full lower levels and a lexicographic initial part of its last level. Its next-level neighbours form the upper shadow of that part. For a set in the next level, its lexicographically earliest lower-level subset is obtained by deleting its largest element. This map preserves the lexicographic order weakly. Membership in the upper shadow is equivalent to that earliest subset belonging to the original initial part, so the upper shadow is an initial part too. Empty and full families satisfy the assertion directly.

Assume the theorem in dimension $n-1$. Split $\mathcal{A}$ into two sections ${\mathcal{A}}_0,{\mathcal{A}}_1$ according to membership of coordinate $i$, deleting $i$ from the second section. Their closed-neighbourhood sections areReplace each section by a simplicial initial segment $I_0,I_1$ of the same size. Induction gives $|N(I_j)|\le |N({\mathcal{A}}_j)|$. By the preceding observation, each $N(I_j)$ is an initial segment and is nested with the other section. Consequentlyand the analogous inequality holds for the other section. Thus simplicial section compression preserves size and cannot increase the closed neighbourhood.

Repeatedly apply a nontrivial section compression. The sum of the positions of the family members in the full simplicial order strictly decreases: the order induced on either fixed-coordinate section is precisely its lower-dimensional simplicial order. This positive integer potential makes the process terminate at a family $\mathcal{B}$ fixed by every section compression.

We classify such terminal families for simplicial section compression. If an earlier vertex $x$ is absent while a later vertex $y$ is present, they cannot agree at any coordinate, since the corresponding section is an initial segment. Hence $y=x^c$. Every other vertex earlier than $y$ is present, and every other vertex later than $x$ is absent, since any further inverted pair would also have to be complementary. There can therefore be no vertex strictly between $x$ and $y$. Thus $\mathcal{B}$ either is an initial segment or is an initial segment with its last vertex replaced by the next, complementary vertex.

The complementary consecutive pairs are explicit. If $n=2r+1$, the ranks must be $r$ and $r+1$, and consecutive order positions forceThe corresponding initial segment $I$ contains all sets of size at most $r$, and $\mathcal{B}=I-\{x\}+\{y\}$. Its closed neighbourhood contains all sets of size at most $r+1$: for $r\ge 1$, deletion of just one $r$-set cannot remove all the $r$-subsets of any $(r+1)$-set, and $x$ remains adjacent to one of its $(r-1)$-subsets. In addition, the $r$ supersets of $y$ of size $r+2$ enter the neighbourhood. Thus $|N(\mathcal{B})|=|N(I)|+r$; the $n=1$ case gives equality directly.

If $n=2r$, the two vertices have rank $r$. Complementation reverses the lexicographic order within that rank, so consecutive complements occupy its middle two positions. These areNow $I$ contains all sets of size less than $r$ and all $r$-sets containing coordinate one. Its closed neighbourhood contains all sets of size at most $r$ and all $(r+1)$-sets containing one. For $r\ge 2$, each such $(r+1)$-set has at least two $r$-subsets containing one, so exchanging $x$ for $y$ loses none of these neighbours. It adds the $r-1$ supersets of $y$ of size $r+1$ that avoid one. Hence $|N(\mathcal{B})|=|N(I)|+r-1$. For $n=2$ the two neighbourhoods are both the entire cube.

In both exceptional cases the initial segment has no larger neighbourhood. The induction starts with the one-vertex zero-dimensional cube, and the compression argument now proves

The four functions theorem concerns nonnegative functions $\alpha ,\beta ,\gamma ,\delta$ on the Boolean lattice. Its pointwise hypothesis and conclusion areWe prove it by eliminating coordinates.

The elementary step is the two-point four-functions inequality. Suppose $a_i{b}_j\le c_{\max (i,j)}{d}_{\min (i,j)}$ for $i,j\in \{0,1\}$. Put $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $R=c_0{d}_1$. Then $x,y\le M$ and, using the two diagonal bounds,If $M>0$, $(M-x)(M-y)\ge 0$ yields $x+y\le M+xy/M\le M+R$. If $M=0$, both cross terms vanish and the same conclusion holds. Adding the diagonal bounds gives

For subsets $S,T\subseteq [n-1]$, take $a_i=\alpha (S\cup E_i)$, $b_j=\beta (T\cup E_j)$, $c_i=\gamma ((S\cup T)\cup E_i)$ and $d_i=\delta ((S\cap T)\cup E_i)$, where $E_0=\varnothing$, $E_1=\{n\}$. The original hypothesis supplies precisely the four inequalities of the elementary step. Therefore the marginal functionsand similarly ${\beta }^{\prime },{\gamma }^{\prime },{\delta }^{\prime }$, satisfy the same pointwise hypothesis on $[n-1]$. Induction, starting with the one-element Boolean lattice on the empty ground set, proves the four functions theorem. This proof includes zero-valued functions without division by zero.

For the Harris-Kleitman inequality, let $\mathcal{F},\mathcal{G}$ be increasing set families, meaning they contain every superset of each member. In the theorem take $\alpha =1_{\mathcal{F}}$, $\beta =1_{\mathcal{G}}$, $\gamma =1_{\mathcal{F}\cap \mathcal{G}}$ and $\delta =1$. If $A\in \mathcal{F}$ and $B\in \mathcal{G}$, their union belongs to both increasing families, so the hypothesis holds. Thus, for the uniform probability measure $\mu$ on subsets,Mapping every subset to its complement proves the same Harris-Kleitman inequality for two decreasing families. An increasing and a decreasing family have the reverse inequality: apply positive correlation to the increasing family and the complement, as a family, of the decreasing one. More generally, increasing nonnegative functions obey the corresponding positive-correlation bound by the same four-functions substitution, since both function values at the union dominate the original values. For an independent-coordinate product measure, multiply all four functions by its weight $w$; the identity $w(A)w(B)=w(A\cup B)w(A\cap B)$ preserves the hypothesis and proves the weighted Harris inequality too.

Finally, replace each intersecting family ${\mathcal{A}}_i$ by its upward closure of a set family ${\mathcal{U}}_i$. It is still intersecting: two supersets of intersecting members have nonempty intersection. It contains at most one of each pair $S,S^c$, and hence $|{\mathcal{U}}_i|\le 2^{n-1}$. Let ${\mathcal{D}}_i$ be the complement of ${\mathcal{U}}_i$ as a family. These families are decreasing and have measure at least one half. Their intersections are decreasing too, so repeated Harris-Kleitman inequality givesTaking complements and using ${\mathcal{A}}_i\subseteq {\mathcal{U}}_i$ proves the union bound for intersecting families:For $k\le n$, equality is attained by the families of sets containing coordinate $i$, $1\le i\le k$. For $k>n$, the displayed real bound implies the integer bound $2^n-1$, which is attained by using the $n$ coordinate families and repeating families as necessary.