Uniform set family ($\mathcal{A}\subseteq [n{]}^{(k)}$)

A $k$-uniform set family consists entirely of $k$-element subsets of a common ground set.

A generating family consists of sets of size at most $r$ whose $r$-element supersets are exactly the prescribed uniform set family. Small-support generators express dependence on a bounded prefix rather than on the full ground set. Taking the entire family itself as generators always works, but extremal intersection problems admit much smaller supporting intervals.

For a t-intersecting family with left-compressed generators supported on $[m]$, a tight pair containing $m$ cannot both miss an earlier coordinate $i$. Replacing $m$ by $i$ in one generator gives a shifted set containing a generator, whose intersection with the other has at most $t-1$ points. Thus the union is $[m]$, and their sizes sum to $m+t$. This identifies precisely which size classes conflict when the largest support coordinate is removed.

Suppose a left-compressed set family of $k$-sets has an antichain of generators on $[m]$, closed under left shifts followed by taking inclusion-minimal members. For a generator $G$ containing $m$, the members generated only by $G$ have intersection with $[m]$ exactly $G$. If another prefix coordinate $i$ occurred, the left shift $G-\{m\}+\{i\}$ would supply another generator. Conversely, an exact prefix $G$ contains no other generator by the antichain condition. The free tail gives the displayed binomial coefficient.

Let $n>2r-t$ and let $G,H$ generate respectively a t-intersecting family of $r$-sets and its complement family. If their union had size at most $n-r+t-1$, contain it in a set $T$ of that size. Since $|T|\ge r,n-r$, extend $G,H$ within $T$ to an $r$-set $A$ and an $(n-r)$-set $B$. Both $A$ and $B^c$ belong to the original family, but $|A\cap B^c|=|A\cup B|-|B|\le t-1$. This contradiction proves the bound.

Assume $1\le t\le r\le n$, $n>2r-t$, and $j\ge 0$. A maximum-cardinality left-compressed set family of $r$-sets that is t-intersecting has a generating family for a uniform set family supported on $[t+2j]$ under the displayed strict inequality. Reflection gives a right-end supporting interval for a right-compressed optimum. The strict threshold is important: at a tie between consecutive candidate families, use the next larger support bound. This auxiliary generating result, combined with the compatibility bound for complementary generating families, supplies the upper bound in the Ahlswede-Khachatrian theorem.

Let $m$ be the smallest supporting prefix for a maximum left-compressed set family of $k$-sets that is t-intersecting, and set $N=n-m$. The maximum-support generator fibre gives exclusive count $\left(\genfrac{}{}{0ex}{}{N}{k-a}\right)$ for a size-$a$ generator containing $m$. By tight pairs of left-compressed generators, only classes $a,b$ with $a+b=m+t$ can conflict after deleting $m$. For unequal such sizes, replacing both classes by the shortened generators of either class would implyWhen $n\ge 2k-t+2$ and the classes have positive fibres, the reverse inequality is strict. For the remaining central class $a=t+j$, $m=t+2j$, some earlier coordinate is absent from at least $j/(m-1)$ of its shortened generators. Those generators are mutually t-intersecting. Replacing the central class by that subfamily has gain-to-loss ratio at leastwhich exceeds one exactly when $n>(k-t+1)(2+(t-1)/j)$. This forces the support bound in the small-support generating lemma for extremal intersecting families.

An intersection-free uniform set family is a uniform set family $\mathcal{F}$ with no three distinct members $A,B,C$ satisfying $A\cap B\subseteq C$. For distinct members of a rank-$r$ family, $|A\cap B|<r$, so using strict containment gives the same restriction. Fixing one member turns the other members' intersections with it into distinct antichain traces, giving the antichain trace bound for intersection-free families.

For an intersection-free uniform set family of rank $r$, fix $X\in \mathcal{F}$. The map $A\mapsto X\cap A$ on $\mathcal{F}\setminus \{X\}$ is injective and its image is an antichain in $\mathcal{P}(X)$: a containment $X\cap A\subseteq X\cap B$ would violate intersection-freeness on the distinct members $X,A,B$. The Sperner theorem then proves the displayed bound.

The uniform layer consists of the characteristic vectors of sets of size $r$ in $[n]$. It has size $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, a binomial coefficient. Restricting polynomials to a uniform layer introduces identities absent on the entire Boolean lattice, since the coordinate sum is fixed. In particular, homogenisation on a uniform layer spans all restricted multilinear polynomials of degree at most $s\le r$ using just the degree-$s$ monomials.

Let $0\le s\le k\le n$ and form the integer matrix with rows indexed by $S\subseteq [n]$, $|S|\le s$, columns indexed by $k$-subsets $T$, and entry $M_{S,T}=1_{S\subseteq T}$. Its matrix rank over any finite field ${\mathbb{F}}_p$ is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Over the rational numbers, the row of a $j$-subset $S$ is ${\left(\genfrac{}{}{0ex}{}{k-j}{s-j}\right)}^{-1}$ times the sum of the rows of all $s$-subsets containing $S$. Thus the rows of degree exactly $s$ span, giving the bound over the rational numbers. Every larger square minor therefore has integer determinant zero, and remains zero modulo $p$. The matrix rank cannot increase under this reduction. This argument avoids dividing by an integer that might vanish in the finite field, and gives the sharp uniform-layer step in the Frankl-Wilson theorem.

If $n\ge 2k$ and $\mathcal{A}\subseteq [n{]}^{(k)}$ is intersecting, then $|\mathcal{A}|\le \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$.

For an intersecting family of $r$-sets with $n\ge 2r$, the rank-$r$ lower shadow of its complement family is disjoint from the original family. Iterating the Kruskal-Katona theorem shows that exceeding $\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$ original members would force this shadow to have more than $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ members, contradicting the total number $\left(\genfrac{}{}{0ex}{}{n}{r}\right)$ of $r$-sets.

Katona's circle method places a finite ground set in a uniformly counted cyclic order, proves a bound for the members of a set family that appear as cyclic intervals, and double-counts pairs of a member and a compatible cyclic order.

In any cyclic ordering on $n$ points, an antichain contains at most $n$ nonempty proper cyclic intervals. The intervals with one prescribed final position are nested, so at most one belongs to the antichain. Summing over final positions proves the bound. Averaging it over cyclic orderings proves the LYM inequality; the empty set and full set must be handled separately.

An intersecting family of cyclic intervals of length $r$ in a cyclic order of $n$ positions has at most $r$ members when $1\le r\le n/2$. Rotate one selected interval to end at position $n$. Intervals ending at $r,\dots ,n-r$ miss it. Pair the remaining endpoints, other than $n$, as $(j,j+n-r)$ for $1\le j\le r-1$; each pair represents two disjoint intervals, hence contributes at most one member. This gives $1+(r-1)=r$. Counting such intervals over all permutations proves the Erdős-Ko-Rado theorem.

A Steiner triple system is a collection of three-element subsets, called blocks, in which every pair of points belongs to exactly one block. Distinct blocks consequently meet in at most one point, and a system on $v$ points has $v(v-1)/6$ blocks.