Set family

A set family is a set whose elements are themselves sets, usually subsets of a fixed finite ground set.

A Helly family of order $k$ is a set family for which every finite subfamily has nonempty total intersection whenever each of its subfamilies with at most $k$ members has nonempty intersection. Convex subtrees of a tree have Helly order two.

For a finite ground set and an indexed set family, this zero-one matrix records membership of points in members. The diagonal entries of $B^{T}B$ are member sizes, and its off-diagonal entries count pairwise intersections. For the Fano plane, either point-line orientation gives the identity $B^{T}B=2I+J$, since every point lies on three lines and each distinct point pair lies on one line.

Suppose $|R_i|=r$, $|S_i|=s$ and $R_i\cap S_j$ is nonempty exactly when $i=j$. Choose $x_i\in R_i\cap S_i$. Each witness lies in neither set of any other pair, so the witnesses are distinct. For two distinct indices, $R_i\setminus \{x_i\}$ and $S_j\setminus \{x_j\}$ are disjoint subsets outside the witness set. Thus $n-|I|\ge r+s-2$. Equality is attained by disjoint fixed cores $P,Q$ of sizes $r-1,s-1$ and distinct remaining witnesses, with $R_i=P\cup \{x_i\}$ and $S_i=Q\cup \{x_i\}$.

For set families, $\mathcal{A}\vee \mathcal{B}=\{A\cup B:A\in \mathcal{A},B\in \mathcal{B}\}$ and $\mathcal{A}\wedge \mathcal{B}=\{A\cap B:A\in \mathcal{A},B\in \mathcal{B}\}$. These are families of distinct sets, rather than multisets indexed by pairs. The four functions theorem gives $|\mathcal{A}\vee \mathcal{B}||\mathcal{A}\wedge \mathcal{B}|\ge |\mathcal{A}||\mathcal{B}|$. Complementing one input family yields the analogous product bound for pairwise set differences.

For nonnegative functions on a finite Boolean lattice, the condition $\alpha (A)\beta (B)\le \gamma (A\cup B)\delta (A\cap B)$ for all pairs implies $(\sum \alpha )(\sum \beta )\le (\sum \gamma )(\sum \delta )$. Coordinate elimination and the two-point four-functions inequality prove it by induction. Indicators give inequalities for the union and intersection of set families. The Boolean-lattice statement appears in Theorem 3.1 of Nicholas Ruozzi's paper.

Suppose nonnegative numbers satisfy $a_0{b}_0\le c_0{d}_0$, $a_1{b}_1\le c_1{d}_1$, and $a_0{b}_1,a_1{b}_0\le c_1{d}_0$. Set $x=a_0{b}_1$, $y=a_1{b}_0$, $M=c_1{d}_0$, $N=c_0{d}_1$. Then $x,y\le M$ and $xy\le MN$. For $M>0$, $(M-x)(M-y)\ge 0$ gives $x+y\le M+xy/M\le M+N$; for $M=0$, $x=y=0$. Adding the two diagonal bounds proves $(a_0+a_1)(b_0+b_1)\le (c_0+c_1)(d_0+d_1)$. This lets the four functions theorem sum out one Boolean coordinate while preserving its pointwise hypothesis.

The biased measure of a set family is its probability when each ground-set element is independently included with probability $p$. If $a_j$ is the proportion of the $j$th level occupied by the family, then ${\mu }_p(\mathcal{F})={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)a_j{p}^j(1-p{)}^{n-j}$. This translates a combinatorial level bound into a probability inequality for independent Bernoulli random variables.

A self-dual set family on $[n]$ contains exactly one of $A,A^c$ for every subset $A$. Its relative proportions $a_j$ in complementary uniform levels satisfy $a_{n-j}=1-a_j$. In particular its measure under a uniform random subset is $1/2$.

Suppose a self-dual set family has level proportions $a_j\le j/n$ for $j<n/2$. Subtract the binomial identity $p={\sum }_j\left(\genfrac{}{}{0ex}{}{n}{j}\right)(j/n)p^j(1-p{)}^{n-j}$ from its biased measure of a set family and pair levels $j,n-j$. The difference isEvery term is nonnegative for $p\ge 1/2$. A self-dual intersecting family has the required level bounds by the Erdős-Ko-Rado theorem.

Let $c_i\ge 0$ sum to one, with no subset sum equal to $1/2$, and let independent Bernoulli random variables $Z_i$ all have parameter $p\ge 1/2$. The subsets of weight greater than $1/2$ form an intersecting self-dual set family. The complementary-layer bound for biased measure proves $\mathbb{P}({\sum }_i{c}_i{Z}_i\ge 1/2)\ge p$. Nonnegative weights ensure that disjoint sets cannot both have weight greater than $1/2$; the no-tie condition supplies self-duality.

A set family is laminar if any two members are disjoint or one contains the other. Its distinct inclusion-maximal members are therefore disjoint. Applied to the true sets in a hierarchical family of intersection hypotheses, this gives the disjoint-block bound used for familywise error control for a laminar hypothesis family.

An elementary union-intersection compression of a finite multiset of subsets replaces occurrences of $A,B$ by $A\cup B,A\cap B$. A compression is a finite sequence of these moves. The move preserves every coordinate multiplicity. On incomparable sets it increases ${\sum }_S|S{|}^2$ by $2|A\setminus B||B\setminus A|$, so repeated compression reaches a chain under inclusion. For any submodular set function, the sum of its values cannot increase.

Two set families $\mathcal{A},\mathcal{B}$ are cross-Sperner when no member of either is a subset of a member of the other, including equality. Thus $\mathcal{A}\cap \mathcal{B}=\varnothing$. Neither family need itself be an antichain. On the Boolean lattice of subsets of $[n]$, the Cross-Sperner inequality bounds $\sqrt{|\mathcal{A}|}+\sqrt{|\mathcal{B}|}$ by $2^{n/2}$.

A set $H$ is a hitting set for a set family $\mathcal{F}$ if $H\cap A\ne \varnothing$ for every $A\in \mathcal{F}$. Every set is a hitting set for an empty set family; none is a hitting set for a family containing the empty set. Bounded hitting sets permit finite certificates for some infinite set families, as in the bounded-size transversal kernel.

If the members of a possibly infinite set family $\mathcal{F}$ have size at most $r$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ of size at most $M(r,s)$ with exactly the same hitting sets of size at most $s$. Use mathematical induction on $s$. For nonempty $\mathcal{F}$, choose $A_0\in \mathcal{F}$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for ${\mathcal{F}}_x=\{A\in \mathcal{F}:x\notin A\}$ at parameter $s-1$, and take their set union together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A hitting set $H$ for this kernel meets $A_0$ at some $x$; $H\setminus \{x\}$ meets the kernel for ${\mathcal{F}}_x$, hence all of ${\mathcal{F}}_x$, while $x$ meets the other members of $\mathcal{F}$. If $A_0$ is empty no hitting set exists, and if $\mathcal{F}$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal{F}$ is needed.

The Boolean lattice is the power set of a finite set ordered by inclusion. Its rank-$h$ level consists of all $h$-element subsets.

A family in the Boolean lattice whose pairwise Hamming distances are at most $d<n$ has size at most $D(n,d)$. Downward compression followed by elementary set shifts preserves the distance bound. In the resulting down-set, the section containing the last coordinate has diameter at most $d-2$: two members leave a coordinate free, and shifting the last coordinate to it creates a pair with two additional disagreements. This gives the recurrence $D(n,d)=D(n-1,d)+D(n-1,d-2)$. The boundary case $d=n-1$ follows by pairing complementary sets. Hamming balls attain the even case; the union of two radius-$q$ balls with adjacent centers attains the odd case.

If $n\ge 2d+1$ and the field characteristic is zero or greater than $d+1$, the matrix recording inclusion of $d$-sets in $(d+1)$-sets has full row rank. Subtracting equations on sets differing in one coordinate reduces the kernel problem to degree $d-1$ on $n-2$ coordinates. Mathematical induction then makes all coefficients equal, and the factor $d+1$ forces them to vanish. This gives the auxiliary-polynomial independence used in the uniform Frankl-Wilson theorem.

An up-set is a family $\mathcal{U}$ such that $A\in \mathcal{U}$ and $A\subseteq B$ imply $B\in \mathcal{U}$.

An up-set is upward closed under inclusion: if $A$ belongs and $A\subseteq B$, then $B$ belongs. This is the Boolean-lattice case of upper and lower sets.

A down-set is a family $\mathcal{D}$ such that $A\in \mathcal{D}$ and $B\subseteq A$ imply $B\in \mathcal{D}$. It is the complement of an up-set within the same Boolean lattice.

This is the downward-closed Boolean-lattice case of upper and lower sets.

For a down-set $D$ in the Boolean lattice, every member $A$ has all its $|A|$ immediate lower neighbors in $D$. Counting an internal edge at its upper endpoint gives $e(D)={\sum }_{A\in D}|A|$. The degree identity for the edge boundary of the hypercube graph then gives the displayed formula.

For a down-set of size $m$, maximize its edge boundary by minimizing the sum of the sizes of its members. Choose all sets in the smallest ranks, followed by any needed part of the next rank; this minimizes that sum among all families and is itself a down-set. With $M_j={\sum }_{i=0}^j\left(\genfrac{}{}{0ex}{}{n}{i}\right)$, $M_{-1}=0$, and $M_{r-1}\le m\le M_r$, the exact maximum is $h(m)=nm-2[{\sum }_{j<r}j(\genfrac{}{}{0ex}{}{n}{j})+r(m-M_{r-1})]$.

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$, its downward closure is $\downarrow \mathcal{A}=\{S:\text{some }A\in \mathcal{A}\text{ has }S\subseteq A\}$. It is the smallest down-set containing $\mathcal{A}$, just as the upward closure of a set family is the smallest up-set containing it. The two closures allow Harris' inequality to control sizes of a cross-Sperner family pair.

An antichain is a family of sets no one of which contains another.

A maximal chain in $\mathcal{P}([n])$ contains one set of every cardinality from zero to $n$, with each set obtained from the preceding one by adding a single element.

A uniformly random maximal chain is obtained from a uniformly random ordering of the ground set by taking its successive initial segments. A fixed $h$-element set occurs with probability ${\left(\genfrac{}{}{0ex}{}{n}{h}\right)}^{-1}$.

If $\mathcal{A}$ is an antichain in $\mathcal{P}([n])$ and ${\mathcal{A}}_h$ is its rank-$h$ part, thenThe left side is the expected number of members of $\mathcal{A}$ on a Uniformly random maximal chain in a Boolean lattice.

An antichain in the Boolean lattice has Lubell mass one if and only if it is a full rank level. Equality means every maximal chain in a Boolean lattice meets the family exactly once. Swapping two adjacent entries in the defining permutation then forces the family to contain every set obtained from one member by exchanging an included and an excluded element, hence every set of that rank.

The Lubell mass of a set family $\mathcal{A}\subseteq \mathcal{P}([n])$ isIt is the expected value of the number of members of $\mathcal{A}$ on a Uniformly random maximal chain in a Boolean lattice.

For $\mathcal{A}\subseteq [n{]}^{(r)}$, the local LYM inequality saysIt follows by counting pairs $(B,A)$ with $B\subset A$, $|B|=r-1$, and $A\in \mathcal{A}$.

The bipartite inclusion graph between consecutive nonempty ranks of the Boolean lattice is connected. Two rank-$r$ sets differing by one exchanged element share their rank-$(r+1)$ union as a neighbour; successive exchanges connect any two rank-$r$ sets. Every upper vertex has a lower neighbour. For the two middle ranks of an odd-dimensional Boolean lattice the graph is regular, so equality in the Local LYM inequality for a nonempty upper family forces the whole upper rank: equality admits no edges from its lower shadow to the remaining upper vertices.

Repeatedly applying the Local LYM inequality to upper shadows givesfor $\mathcal{A}\subseteq [n{]}^{(r)}$ and $0\le s\le n-r$. The analogous statement for iterated lower shadows follows directly from the stated lower-shadow form.

Every antichain in $\mathcal{P}([n])$ has at most $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ members. Equality is attained only by a full middle level, with either middle level possible when $n$ is odd.

For vectors of norm at least one, the number of signed sums in an open unit ball is at most the central binomial coefficient. In one dimension this follows from the antichain bound. In Euclidean spaces a separated block decomposition for vector subset sums supplies the same bound without assuming all vectors have positive projection in one common direction. Signed sums are counted with multiplicity, by their sign choices.

For real coefficients of absolute value at least one, an open interval of length four contains at most the sum of the two largest binomial coefficients of signed sums. The corresponding subset family has no three-element inclusion chain. Its Lubell mass is therefore at most two, giving the bound by allocating mass to the two largest levels. Unit coefficients attain it at a center midway between the two chosen sum levels.

For Euclidean vectors $x_i$ of length at least one, their labeled subset sums can be partitioned into pairwise distance-at-least-one blocks, with $\left(\genfrac{}{}{0ex}{}{n}{r}\right)-\left(\genfrac{}{}{0ex}{}{n}{r-1}\right)$ blocks of size $n-2r+1$. To extend a separated block by a vector $x$, choose its member $y$ minimizing inner product with $x$. The translated block together with $y$ remains separated, since $(z+x-y)\cdot x\ge \Vert x{\Vert }^2$. The untransformed block with $y$ removed remains separated too. Block sizes change from $\ell$ to $\ell +1,\ell -1$, the same recurrence as a symmetric chain decomposition of a Boolean lattice. There are exactly $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ nonempty blocks.

The maximum antichains in the Boolean lattice are exactly its full middle levels. For even $n$ there is one such level, and for odd $n$ either middle level works. The LYM inequality first confines a maximum antichain to those levels; connectedness of the regular inclusion bipartite graph rules out a mixture of the two odd middle levels.

A $k$-Sperner family contains no inclusion chain of length $k+1$. Every maximal chain in a Boolean lattice therefore meets it in at most $k$ members, so its Lubell mass is at most $k$.

For positive weights $w(i)$ depending only on rank, put $u_i=\left(\genfrac{}{}{0ex}{}{n}{i}\right)w(i)$. The largest weight of a k-Sperner family in $\mathcal{P}([n])$ is the sum of the $k$ largest $u_i$. Every maximizing family is a union of $k$ full rank levels. To see the equality assertion, its Lubell mass must be $k$; decomposing it into $k$ antichains by chain height and using equality in the LYM inequality forces each part to be a full level.

If $t$ is the $k$th largest rank weight $u_i$, exactly $h$ levels have weight greater than $t$, and exactly $s$ have weight $t$, then there are $\left(\genfrac{}{}{0ex}{}{s}{k-h}\right)$ maximizing families. For fixed $n,k$, the possible counts are exactly $\left(\genfrac{}{}{0ex}{}{s}{j}\right)$ with $1\le j\le k$ and $j\le s\le n+1-k+j$.

Among $k$-Sperner subfamilies of $\mathcal{P}([n])$, the maximum cardinality is the sum of the $k$ largest binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The union of the corresponding levels attains the bound. For the upper bound, the Lubell mass is at most $k$, and assigning its available mass to the levels with largest binomial coefficients maximizes cardinality.

If set families $\mathcal{A},\mathcal{B}\subseteq \mathcal{P}([n])$ are cross-incomparable, meaning no member of either contains a member of the other, thenThe proof applies the Harris-Kleitman inequality to the upward closures generated by the two families.

Choose disjoint subsets $K_1,K_2\subseteq [n]$ of size $k\ge 1$ with $2k\le n$. Let $\mathcal{A}$ consist of subsets containing all of $K_1$ and none of $K_2$; let $\mathcal{B}$ consist of subsets omitting at least one point of $K_1$ and containing at least one point of $K_2$. These form a cross-Sperner family pair, with sizes $2^{n-2k}$ and $(2^k-1{)}^2{2}^{n-2k}$. Their square roots sum to $2^{n/2}$, proving sharpness of the Cross-Sperner inequality. The free coordinates outside the two blocks account for the factor $2^{n-2k}$.

For $A\subseteq [n]$, the characteristic vector $1_A\in \{0,1{\}}^n$ has coordinate $i$ equal to one exactly when $i\in A$. Under this identification, set union becomes coordinatewise Boolean OR.

Over ${\mathbb{F}}_2$, characteristic vectors satisfy $1_A\cdot 1_B=|A\cap B|\mathrm{mod}2$. Parity restrictions on sizes and intersections therefore become diagonal and off-diagonal conditions on a Gram matrix, allowing rank and linear-independence arguments.

The incidence graph of a set family is the bipartite graph whose two vertex classes are the family members and the ground points, with an edge for each containment relation.

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$ and $F\subseteq [n]$, its trace on $F$ is

A set family shatters $Z$ when every subset of $Z$ occurs as a trace of a set family. The largest finite shattered-set size is its VC dimension. The Sauer-Shelah lemma bounds the number of traces when no set of a given size is shattered.

Partition an infinite countable set into disjoint finite blocks of unbounded size. The union of their power sets consists entirely of finite sets and shatters each block, so it has unbounded finite VC dimension. Every infinite set meets two different blocks. The pair formed by one point from each can never occur as a trace, since each family member stays in one block. Thus no infinite set has traces realizing all its finite subsets.

If every ground element belongs to at least $t$ members of a family $\mathcal{F}\subseteq \mathcal{P}([n])$, thenApply Shearer's inequality to the characteristic vector of a uniformly random member of $\mathcal{A}$.

A set family $\mathcal{A}$ is union-closed when $A\cup B\in \mathcal{A}$ for every $A,B\in \mathcal{A}$.

The union-closed sets conjecture states that every finite nontrivial union-closed family has an element contained in at least half of its members.

For $x,y\in [0,1]$, the binary entropy and the golden ratio $\phi$ satisfy

Every finite union-closed family other than $\{\varnothing \}$ has an element belonging to at leastof its members. The proof applies the binary entropy product inequality coordinate by coordinate to the union of two independent uniform members of the family.

Let $A_1,\dots ,A_m$ be random subsets of a common ground set. If every pairwise union $A_i\cup A_j$ takes values in a fixed family $\mathcal{A}$ of sets of cardinality at most $k$, then Shearer's inequality and the fact that a pair of bits with prescribed OR has at most three possibilities give

A family of sets is intersecting when every two of its members have nonempty intersection.

This is a property of a set family, distinct from extremal theorems bounding its size.

For intersecting families of subsets of $[n]$, take each upward closure of a set family. It remains intersecting and contains at most one set in each complementary pair, so its complement as a family has density at least one half. Those complements are decreasing set families. Repeated Harris-Kleitman inequality gives intersection density at least $2^{-k}$, proving the displayed bound. For $k\le n$, the families of sets containing coordinate $i$, for $1\le i\le k$, attain equality.

On five points, the four sets $12,13,14,15$ are an intersecting family. The first four two-element sets in colexicographic order are $12,13,23,14$, containing the disjoint pair $23,14$. Thus replacing a family by an equally large colexicographic initial segment can destroy intersection, even though it minimizes the lower shadow.

For $1\le r\le n/2$, the Erdős-Ko-Rado theorem bounds an intersecting family by the displayed size. The first that many rank-$r$ sets in lexicographic order all contain coordinate one. Therefore the lexicographic initial segment of the same size as any intersecting family is also intersecting. This statement concerns ordinary one-element intersection and does not extend to higher intersection requirements.

A maximal intersecting family is an up-set. It cannot contain both a set and its complement. If neither were present, maximality would supply a member disjoint from the first set, and upward closure would then include its complement. Thus precisely one member of each complementary pair occurs, so the family has $2^{n-1}$ members for $n\ge 1$.

A set family is t-intersecting if every pair of its members has at least $t$ common elements. For $r$-sets on an $n$-point ground set, the whole level is t-intersecting when $n\le 2r-t$. Ordinary intersecting families are the case $t=1$.

On eight points, the rank-four Frankl family consisting of sets containing at least three of $1,2,3,4$ has seventeen members and is two-intersecting. The first fifteen rank-four sets in lexicographic order contain $1,2$, while the sixteenth is $1345$. The earlier set $1278$ meets it only at one. This disproves preservation of two-intersection by lexicographic replacement even when the rank is half the ground-set size.

For two-intersecting families on four points, all supersets of a fixed pair form a maximal family of size four: any set missing part of that pair fails its intersection test with the pair itself. The maximum instead has size five, attained by all sets of size at least three. Thus maximality and maximum cardinality diverge for intersection parameter two.

If $|A\cap B|\ge t$, then $|A△B|=|A\cup B|-|A\cap B|\le n-t$. The Kleitman diametric theorem therefore gives the sharp nonuniform intersection bound. For $n-t=2q$, all sets of size at least $n-q$ attain it. For $n-t=2q+1$, take all sets of size at least $n-q$, together with all $(n-q-1)$-sets avoiding one fixed point.

The maximum size of a t-intersecting family of $r$-sets on $[n]$ is the largest complete-intersection candidate family. In strict nontrivial intervals $n_{k+1}<n<n_k$, the maximizing index is $k$, where $n_k=(r-t+1)(2+(t-1)/k)$ and $n_0=\infty$. At admissible interior boundaries the consecutive candidates tie. If $n\le 2r-t$, the whole level is optimal. A proof uses left compression, the small-support generating lemma for extremal intersecting families for the original and complement families, and the compatibility bound for complementary generating families. The latter forces one generator family to have the candidate threshold size, placing the original family inside a candidate.

Complementing all members preserves cardinality and gives $|A^c\cap B^c|=n-2r+|A\cap B|$. Thus complementation bijects t-intersecting families of $r$-sets with $(n-2r+t)$-intersecting families of $(n-r)$-sets. It swaps left and right coordinate shifts of a set family. When the transformed intersection parameter is positive, extremal families and their generating-support lemmas can therefore be compared in opposite compression directions.

Two members of this uniform set family have at least $2(t+i)-(t+2i)=t$ common points in its distinguished prefix, so it is a t-intersecting family. Nonempty indices satisfy $0\le i\le r-t$. Consecutive-family size comparison reduces to the threshold $n_{i+1}=(r-t+1)(2+(t-1)/(i+1))$: gain sets contain both newly introduced coordinates and $t+i-1$ earlier points; loss sets contain neither and $t+i$ earlier points. Counting these sets with binomial coefficients proves increase below, equality at and decrease above this threshold.

A pairwise intersecting family of two-element sets is contained in a star graph or in the three edges of a triangle in a graph. If two members are $\{a,b\},\{a,c\}$ and a third avoids $a$, the third must be $\{b,c\}$. Every member meeting all three belongs to that triangle.

For an intersecting family of $r$-sets, some element $x$ is avoided by at most $(r-1{)}^2(\genfrac{}{}{0ex}{}{n-2}{r-2})$ members. If two members meet exactly at $x$, every member avoiding $x$ contains one element from each of their disjoint remainders. If no such pair exists, apply the pair-cover bound for a two-intersecting uniform family.

A set family is two-intersecting if $|A\cap B|\ge 2$ for all of its members, including $A=B$. In particular its members all have at least two elements. This is stronger than being an intersecting family.

Fix a member of size $r$. Every other member of a two-intersecting family contains a pair from that fixed member. Counting all $r$-sets containing these pairs gives $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{r}{2}\right)\left(\genfrac{}{}{0ex}{}{n-2}{r-2}\right)$ for a uniform set family.

On an even ground set $n=2h$, a two-intersecting family has size at most ${\sum }_{j=h+1}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. On an odd ground set $n=2h+1$, the bound is $\left(\genfrac{}{}{0ex}{}{2h}{h+1}\right)+{\sum }_{j=h+2}^n\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. Pair lower levels with complements of upper levels using the intersecting shadow lemma; apply the Erdős-Ko-Rado theorem to the remaining middle level in the odd case.

For an intersecting family of $r$-sets with $r\ge 1$, its lower shadow has at least as many members as the family. Apply elementary set shifts and then the ballot reflection injection to obtain this bound.

For odd $n$ and $w\ge 1$, an intersecting family contains at most one set from each complementary pair in the Boolean lattice. Choosing the larger member in every pair gives the displayed bound and is feasible, because all sets of size greater than $n/2$ intersect. For $w>1$ it is the unique maximizer; for $w=1$ other maximizing families can exist.

A family of words in $[k{]}^n$ is intersecting if any two words agree in some coordinate. For positive $n,k$, its maximum size is $k^{n-1}$: simultaneous cyclic shifts partition the words into classes in which distinct words never agree, and fixing one coordinate attains the resulting bound.

An exactly one-intersecting family satisfies $|A\cap B|=1$ for every two distinct members. It is nontrivial when the intersection of all its members is empty.

A finite linear space consists of finitely many points and proper subsets called lines such that every two points lie on exactly one line. The sets of family indices containing each ground point turn a nontrivial exactly one-intersecting family into a finite linear space.

It is a finite nontrivial instance of a Linear space.

If $r_x$ denotes the number of lines through $x$ in a nontrivial finite linear space on $v$ points, thenTo prove it, let $k_L$ be the line sizes. The inequalities $k_L\le r_x$ whenever $x\notin L$, counted at each integer threshold, givefor every $t\ge 1$. Summing in $t$ and using $\left(\genfrac{}{}{0ex}{}{s}{2}\right)={\sum }_{t\ge 1}(s-t{)}_{+}$ giveswhere the last identity counts pairs of points by their unique line.

A near-pencil on $v$ points has one line containing $v-1$ points and $v-1$ two-point lines joining the remaining point to each point of the large line.

This is a particular finite linear space configuration, rather than a synonym for every pencil of lines.

A finite projective plane of order $q$ has $q^2+q+1$ points and the same number of lines. Every line contains $q+1$ points, every point lies on $q+1$ lines, and every two points or two lines determine a unique line or intersection point respectively.

Two set families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting when $A\cap B\ne \varnothing$ for every $A\in \mathcal{A}$ and $B\in \mathcal{B}$.

For cross-intersecting families $\mathcal{A},\mathcal{B}$ with member sizes at most $r,s$ respectively, there is a finite set $X$ with $|X|\le r{\sum }_{j=0}^s{r}^j$ such that $A\cap B\cap X\ne \varnothing$ for every $A\in \mathcal{A},B\in \mathcal{B}$. Take a bounded-size transversal kernel ${\mathcal{A}}_0$ preserving hitting sets of size at most $s$ and set $X={\bigcup }_{A\in {\mathcal{A}}_0}A$. For each $B$, the set $B\cap X$ is a hitting set for ${\mathcal{A}}_0$, hence for all of $\mathcal{A}$. This proves the assertion even for infinite set families; if either family is empty, take $X=\varnothing$.

The upward closure of $\mathcal{B}$ is $\overline{\mathcal{B}}=\{A:\text{some }B\in \mathcal{B}\text{ satisfies }B\subseteq A\}$.

For $0<p<1/2$ and $\epsilon >0$, every intersecting family is, up to ${\mu }_p$-measure $\epsilon$, contained in the upward closure of a set family generated by an intersecting family on a bounded set of coordinates.

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.