Extremal set theory

Extremal set theory asks how large a family of finite sets can be under prescribed intersection or containment restrictions.

If every member of a set family on $[n]$ and every distinct pairwise intersection has even size, its characteristic vectors span a self-orthogonal binary subspace. The standard dot product is nondegenerate, so $W\subseteq W^{\perp }$ implies $2\dim W\le n$. Thus the set family has at most $2^{\lfloor n/2\rfloor }$ members. All unions of $\lfloor n/2\rfloor$ disjoint pairs of points attain this bound.

If all members of a set family on $[n]$ have odd size and all distinct pairwise intersections have even size, its characteristic vectors over the finite field ${\mathbb{F}}_2$ are linearly independent. Their pairwise dot products are zero, and each vector has dot product one with itself. Taking the dot product of a linear combination with each vector makes every coefficient vanish, so there are at most $n$ vectors. The set family of all singleton sets attains this bound.

A set family on a finite set separates ordered pairs if each ordered pair of distinct points has a member containing the first point and omitting the second. If its members are $A_1,\dots ,A_m$, assign each point the characteristic vector of its incidences, or equivalently $T_i=\{a:i\in A_a\}$. Separation in both directions says precisely that the $T_i$ form an antichain in the Boolean lattice on $m$ coordinates. Thus the Sperner theorem gives $n\le \left(\genfrac{}{}{0ex}{}{m}{\lfloor m/2\rfloor }\right)$. Conversely, any antichain of $n$ distinct subsets of $[m]$ supplies such a set family by transposing its incidence table.

If a forbidden intersection size exceeds $n/2$, every subset of size at most $\lfloor n/2\rfloor$ avoids it, including on self-intersection. This set family contains at least half the Boolean lattice. Consequently a fixed exponential bound $c^n$ with $c<2$ cannot hold uniformly as $n$ grows. Forbidden-intersection estimates below the middle rank therefore cannot simply be extrapolated to high intersections.

For two set families forbidding all cross-intersections in $[a,b]$, split into absent and present coordinate sections. The section pairs $({\mathcal{F}}_1,{\mathcal{G}}_1)$, $({\mathcal{F}}_0,{\mathcal{G}}_0\cup {\mathcal{G}}_1)$, and $({\mathcal{F}}_1,{\mathcal{G}}_0\cap {\mathcal{G}}_1)$ forbid, respectively, $[a-1,b-1]$, $[a,b]$, and $[a-1,b]$ in one fewer dimension. For $0<\delta \le 1/10$, either one of the first two pairs, allowing exchange of the set family names, increases the density product by at least $1+\delta$, or the third widens the interval and retains at least $1-\delta -2{\delta }^2$ of that product. This converts a single forbidden intersection into a long forbidden interval while recording every density gain and loss.

Let two set families on $n$ coordinates forbid cross-intersection size $\ell$, and let $\rho$ be their density product. For $0<\delta \le 1/10$, put $g=\log (1+\delta )$, $h=-\log (1-\delta -2{\delta }^2)$, and $D=g+h$. Repeated forbidden-intersection density increments terminate when one endpoint of the forbidden interval reaches zero or the remaining dimension. In the first case, if $v$ steps widened the interval, the cross-intersection bound from cube separation gives $\log \rho \le -g\ell +Dv-v^2/n\le -g\ell +D^{2}n/4$. In the second case, at least $n-\ell$ steps occurred and at most $\ell$ widened, giving $\log \rho \le -gn+(2g+h)\ell$. For a single set family take the square of its density. Choosing $\delta =1/50$ proves $|\mathcal{A}|\le 1.999^n$ for forbidden intersections $n/4$ and $\lfloor n/8\rfloor$, with small dimensions handled directly.

For a nonempty degree-$m$ layer of a down-set in an $N$-element Boolean lattice, the unique real number $x_m\ge m$ with $|{\mathcal{F}}_m|=\left(\genfrac{}{}{0ex}{}{x_m}{m}\right)$ measures an effective number of available coordinates. The Lovász shadow bound and $\partial {\mathcal{F}}_{m+1}\subseteq {\mathcal{F}}_m$ imply $x_{m+1}\le x_m$ whenever the later layer is nonempty. It is a real parameter, not the actual size of the set family's support.

For a down-set on $N$ coordinates, let $p_m=|{\mathcal{F}}_m|/(\genfrac{}{}{0ex}{}{N}{m})$. For $1\le m<N$ with $p_m>0$, the effective ground-set parameter of a hereditary uniform layer gives the displayed ratio bound. Iteration is valid up to the first empty layer. In particular, whenever $2m\le N$, $p_{2m}\le p_m^2$; if the later layer is empty this conclusion is immediate. Ratios with $p_m=0$ are undefined and must be replaced by the assertion that all later layers are empty.

For distinct coordinates $i,j$, replace a member containing $j$ but not $i$ by its partner with $j$ exchanged for $i$, provided that partner is absent. This set family operation preserves cardinality. Repeating shifts with $i<j$ terminates because every change decreases ${\sum }_{A\in \mathcal{F}}{\sum }_{a\in A}a$. Its effect on shadows is described by coordinate-shift shadow containment.

In a set family, replace a set containing $i$ by its deletion of $i$ only when that deletion is absent. This preserves cardinality and cannot increase maximum pairwise Hamming distance. If a new set and a retained set gave a larger distance, the retained set's deletion would already have been present; that deletion and the original uncompressed set would give the same distance. Repeated downward compressions yield a down-set.

For a family in the $n$-dimensional Boolean lattice, the loss of trace cardinality on deleting coordinate $i$ equals the number of pairs $S,S\cup \{i\}$ both in the family. If every direction has at least two such edges, downward coordinate compression preserves that property. The resulting down-set contains the empty set and all $n$ singletons. Each coordinate must also occur in a two-element member. Those pairs cover all $n$ coordinates and number at least $\lceil n/2\rceil$, giving the bound. For $n\ge 2$, the empty set, all singletons and a minimum collection of pairs covering every coordinate attain it.

For a uniform set family, the lower shadow of its shifted set family is contained in the shifted lower shadow. Check the witness in the four patterns of membership in coordinates $i,j$. A surviving shadow member containing only $j$ must have both old shadow partners; a member containing only $i$ needs either old partner. Taking complements exchanges $C_{ij}$ with $C_{ji}$ and gives the same containment for the upper shadow. Thus coordinate shifts of a set family cannot increase either shadow or their disjoint union, the external vertex boundary of a uniform set family.

If distinct members of a set family on $[n]$ have intersection size $\lambda$, then its size is at most $n$ for $\lambda >0$, and at most $n+1$ for $\lambda =0$, assuming $n\ge 1$. In the positive case, use the Gram matrix of the characteristic vectors of sets; a member of size $\lambda$ is handled by disjoint remainders. In the zero case nonempty members are disjoint.

Let $m\ge t\ge 3$ distinct sets have every $t$-fold intersection of size $\lambda$. Either all contain a common set of size $\lambda$, or $m\le k+t-2$, where $k$ is the minimum size of a $(t-2)$-fold intersection. Fix such a minimum intersection and restrict the remaining sets to it. Equal traces give the common set; distinct traces satisfy the constant-intersection family bound. The qualification $m\ge t$ excludes vacuous counterexamples.

The sets $A_i=[m]\setminus \{i\}$ have every $t$-fold intersection of size $m-t$ and every $(t-2)$-fold intersection of size $m-t+2$. For $m\ge t+1$, their common intersection is empty and they attain $m=k+t-2$ in the constant t-wise intersection dichotomy.

For $i<j$, replace a member $A$ containing $j$ but not $i$ by $(A\setminus \{j\})\cup \{i\}$ only when the replacement is absent. An elementary set shift preserves family size and the intersecting family property. The inclusion $\partial (S_{ij}\mathcal{F})\subseteq S_{ij}(\partial \mathcal{F})$ shows that it cannot increase the lower shadow.

A set family is shifted if every elementary set shift leaves it unchanged. For a uniform set family, this is equivalent to downward closure under componentwise comparison of the increasing lists of its elements. Repeated elementary set shifts terminate at a shifted set family.

For a member of a shifted set family that is an intersecting family, find the first prefix with more selected than unselected positions. Reflect membership in that prefix. The result has one fewer element and lies in the lower shadow; the first prefix with more unselected positions gives the inverse. This injection proves the intersecting shadow lemma.

Appending a coordinate one to each indicator vector changes every odd cross-intersection dot product into an even one in ${\mathbb{F}}_2^{n+1}$. The argument for the even cross-intersection bound then gives the displayed bound. It is a valid bound without a claim that it is sharp.

If every cross-intersection of two set families on $[n]$ has even size, the spans of their indicator vectors are orthogonal in ${\mathbb{F}}_2^n$. The orthogonal complement over the binary field dimension formula bounds the sum of their dimensions by $n$, giving the displayed cardinality bound.

Here two words must both have symbols greater than one in some common coordinate, without requiring the symbols to agree. Their supports $S(x)$ therefore form an intersecting family. The fibre of a support of size $r$ contains $(k-1{)}^r$ words, relating this problem to a weighted set family problem.

For disjoint pairs $A_i,B_i$ such that $A_i\cap B_j\ne \varnothing$ whenever $i\ne j$, the displayed sum is at most one. In a uniformly random permutation, the events that all of $A_i$ precedes all of $B_i$ are disjoint events, and their probabilities are the summands. Taking $B_i$ to be the complement of the members $A_i$ of an antichain recovers the LYM inequality.

A family $(A_i,B_i{)}_{i=1}^m$ of pairs of disjoint subsets of a finite set separates its points if each two distinct points lie on opposite sides of at least one pair. Empty sides are allowed by this definition. Let $d(x)$ count pairs containing $x$. Associate to $x$ the subcube of $\{0,1{\}}^m$ fixing coordinate $i$ to zero on $A_i$ and one on $B_i$. Separation makes these subcubes disjoint and yields the disjoint subcube packing inequality.

Pairwise disjoint subcubes of $\{0,1{\}}^m$ fixing $d_1,\dots ,d_n$ coordinates satisfy ${\sum }_{x=1}^n{2}^{-d_x}\le 1$. By Jensen inequality, their average codimension is at least ${\log }_{2}n$. Consequently a separating family of disjoint set pairs of total incidence at most $\lambda mn$, with $\lambda >0$, has $m\ge \lceil {\log }_{2}n/\lambda \rceil$.

A symmetric chain in the Boolean lattice $\mathcal{P}([n])$ contains one set of each size from $r$ through $n-r$. A symmetric chain decomposition partitions the Boolean lattice into such chains.

A symmetric chain contains one subset of each size from $k$ to $n-k$, nested by inclusion. Its endpoint ranks sum to $n$. A symmetric chain decomposition of a Boolean lattice partitions all subsets into such chains.

For $1\le i\le n/2$, the inclusion graph between ranks $i-1$ and $i$ of $\mathcal{P}([n])$ has a matching saturating rank $i-1$. Indeed, each lower vertex has degree $n-i+1$, each upper vertex has degree $i$, and edge counting givesfor every family $\mathcal{A}$ in the lower rank. This verifies the condition of the Hall marriage theorem.

The least number of chains partitioning $\mathcal{P}([n])$ is the size of its largest rank:The middle rank gives the lower bound because a chain contains at most one member of any rank. Compatible adjacent-level matchings give a symmetric chain decomposition attaining the bound.

For equal-size subsets $A$ and $B$ of an ordered ground set, $A$ precedes $B$ in lexicographic order when the smallest element of their symmetric difference belongs to $A$.

For equal-size finite subsets $A$ and $B$, $A$ precedes $B$ in colexicographic order when the largest element of their symmetric difference belongs to $B$.

The first $a$ sets of a fixed size in colexicographic order form a colexicographic initial segment. Its lower shadow is again a colexicographic initial segment at the next smaller size.

A shadow moves a uniform set family to an adjacent level of the subset lattice by deleting or adding one element.

The lower shadow of $\mathcal{A}\subseteq [n{]}^{(r)}$ is

Repeatedly take the lower shadow of a uniform set family. After $j$ steps the result consists of all subsets of its members whose size is $j$ smaller. Iterating the Kruskal-Katona theorem shows that colexicographic initial segments minimize every iterated lower shadow.

For the uniform set family of vertex sets of $r$-cliques, its $(r-2)$-fold lower shadow consists of graph edges. Repeated use of the Kruskal-Katona theorem bounds clique count from edge count. Sixteen four-cliques have at least twenty-three triples in their shadow and at least eighteen edges in their second shadow, by the expansions $16=\left(\genfrac{}{}{0ex}{}{6}{4}\right)+\left(\genfrac{}{}{0ex}{}{3}{3}\right)$ and $23=\left(\genfrac{}{}{0ex}{}{6}{3}\right)+\left(\genfrac{}{}{0ex}{}{3}{2}\right)$. Hence a graph with fifteen edges has at most fifteen four-cliques, attained by the complete graph on six vertices.

IfthenInitial segments of colexicographic order attain equality.

Minimum-shadow families need not be unique up to permutation. Four edges of a four-cycle and the first four pairs in colexicographic order both have four vertices in their lower shadow, but the latter graph has a triangle. For triples, the six sets consisting of two points from $\{1,2,3\}$ and one from $\{4,5\}$ have a nine-pair shadow. The initial six colex triples also have shadow size nine, but their point degrees are $5,4,4,3,2$ instead of $4,4,4,3,3$.

For a nonempty $r$-uniform set family, define $x>r-1$ by $|\mathcal{F}|=\left(\genfrac{}{}{0ex}{}{x}{r}\right)$ using real binomial coefficients. Then its lower shadow has at least $\left(\genfrac{}{}{0ex}{}{x}{r-1}\right)$ members. This continuous estimate is often easier to use than the exact integer expansion in the Kruskal-Katona theorem.

A short proof uses coordinate shifts of a set family. In a fully left-shifted set family split at coordinate one into ${\mathcal{F}}_0$ and ${\mathcal{F}}_1$, deleting one in the present section. The shifting property implies $\partial {\mathcal{F}}_0\subseteq {\mathcal{F}}_1$, and the total lower shadow has size $|{\mathcal{F}}_1|+|\partial {\mathcal{F}}_1|$. Induct on uniformity and, at fixed uniformity, on set family size. If $|{\mathcal{F}}_1|<\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, the Pascal's identity and the size mathematical induction force $|\partial {\mathcal{F}}_0|>\left(\genfrac{}{}{0ex}{}{x-1}{r-1}\right)$, a contradiction. The uniformity mathematical induction applied to ${\mathcal{F}}_1$, followed by the Pascal's identity, proves the estimate. Integer $x$ is sharp for the full $r$-level on $x$ coordinates.

Split a uniform set family into the section avoiding a coordinate and the section containing it, with that coordinate removed. Replace each section by a colexicographic initial segment of the same size. Induction on the ground-set size, and nesting of initial segments, show that this operation cannot enlarge the lower shadow.

Let $f_r(m)$ be the lower-shadow size prescribed by the binomial representation in the Kruskal-Katona theorem. ThenInduction using Pascal's identity proves the inequality and drives the standard ground-set induction for the theorem.

Let $U,V\subseteq [n]$ be disjoint and have the same cardinality. For a set $A$, its $UV$-compression isFor a uniform set family $\mathcal{A}$, a member is replaced only when its image is absent from $\mathcal{A}$; this convention preserves the family's cardinality.

Let $U,V$ be disjoint, equally sized, nonempty sets, with $\min U<\min V$. Suppose an intersecting family is unchanged by all such UV-compressions of smaller size. Then its $(U,V)$-UV-compression is still an intersecting family. Indeed, a newly moved member $A^{\prime }=(A\setminus V)\cup U$ can only be disjoint from a retained old member $B$, since two newly moved members share $U$. Here $B\cap U=\varnothing$ and $V^{\prime }=B\cap V\ne \varnothing$. If $V^{\prime }=V$, retaining $B$ forces $(B\setminus V)\cup U$ to have been present, contradicting the old intersection property with $A$. Otherwise choose $U^{\prime }\subset U$ with $|U^{\prime }|=|V^{\prime }|$ and $\min U\in U^{\prime }$. Stability under the smaller $(U^{\prime },V^{\prime })$-UV-compression forces $(A\setminus V^{\prime })\cup U^{\prime }$ to be present; this member is disjoint from $B$, again a contradiction. Repeatedly applying a changing UV-compression of smallest size terminates, since the sum of lexicographic order positions decreases. A terminal set family is a lexicographic initial segment: a missing earlier member $X$ and present later member $Y$ would be moved by $U=X\setminus Y$, $V=Y\setminus X$.

A set family is left-compressed when replacing a member $j$ by a missing smaller element $i<j$ always produces another member. Equivalently, it is fixed by every $\{i\},\{j\}$-compression with $i<j$.

Suppose that for every $x\in U$ there is a $y\in V$ such that $\mathcal{A}$ is fixed by the smaller compression $C_{U\setminus \{x\},V\setminus \{y\}}$. ThenIndeed, deleting an element outside $U$ from a newly compressed member gives the $UV$-compression of an old shadow member. If the deleted element is $x\in U$, stability under the chosen smaller compression shows that the resulting set already belongs to the old lower shadow. Thusand compression preserves cardinality.

If a uniform family is not an initial colexicographic segment, choose a nontrivial $UV$-compression with $\max U<\max V$ and with $|U|$ minimal. The minimal choice supplies the smaller-compression hypotheses of the Shadow lemma for UV-compressions, so the operation does not increase the lower shadow. It strictly decreases the integer weightbecause the largest element of $U\cup V$ belongs to $V$. Iteration therefore terminates. A terminal family must be an initial colexicographic segment: otherwise an earlier absent set and a later present set supply one more admissible compression. The shadow of that segment has the size in the Kruskal-Katona theorem, proving the theorem.

The upper shadow of $\mathcal{A}\subseteq [n{]}^{(r)}$ isAmong families of fixed size, an initial lexicographic segment minimizes its upper shadow.

Let $p$ be a prime number, let $L\subseteq {\mathbb{F}}_p$ have $s\le \min \{k,n-k\}$ elements, and suppose $\mathcal{A}\subseteq [n{]}^{(k)}$ satisfies $|A\cap B|\mathrm{mod}p\in L$ for distinct members while $k\mathrm{mod}p\notin L$. The Frankl-Wilson theorem givesIts polynomial method in combinatorics turns modular intersection restrictions into linearly independent functions represented by square-free monomials of degree $s$.

For a prime number $p$, the vertices are $k$-subsets of $[N]$. An independent set avoids the only off-diagonal intersection congruent to $k$ modulo $p$, so the Frankl-Wilson theorem bounds its size by $\left(\genfrac{}{}{0ex}{}{N}{p-1}\right)$. A clique has constant intersection $p-1$ and has size at most $N$, by the same theorem modulo a prime larger than $k$. This explicit graph gives an asymmetric Ramsey number lower bound and an exponential chromatic number lower bound.

If member sizes modulo a prime number $p$ avoid $L$ while distinct intersections lie in $L$, evaluation at characteristic vectors of sets gives a diagonal matrix with nonzero diagonal. After multilinear reduction on the Boolean cube, these polynomials remain linearly independent and have degree at most $|L|$. Counting square-free monomials proves $|\mathcal{F}|\le {\sum }_{j=0}^{|L|}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. On a fixed uniform layer, the low-degree evaluation rank on a uniform layer sharpens this to $\left(\genfrac{}{}{0ex}{}{n}{|L|}\right)$ when $|L|$ does not exceed the layer rank.

For a prime $p$, take rank-$2p$ subsets of $[4p]$ with no distinct pair meeting in $p$ points. Split by membership of coordinate one. In the containing part, remove that coordinate; in the avoiding part, first take complements and then remove it. Both transformed families have rank $2p-1$ on $4p-1$ points. Their distinct intersections avoid residue $p-1$ modulo $p$. The uniform Frankl-Wilson theorem bounds each by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$, yielding the displayed stronger form of the requested bound.

Fix a $(p+1)$-set $B\subseteq [4p]$. Take every $2p$-set $B\cup X$ with $X$ a $(p-1)$-subset of the remaining $3p-1$ points, together with the complements of all these sets. Within either half, intersections have size at least $p+1$. Across the halves they have size $|X\setminus Y|\le p-1$. Thus no intersection has size $p$, and the two disjoint halves give the displayed family size.

Let $m=p^a$ and let an $r$-uniform set family have no distinct pair whose intersection is congruent to $r$ modulo $m$. Its size is bounded as displayed; the customary nontrivial form $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)$ requires $m-1\le r$. The Lucas theorem makes $\left(\genfrac{}{}{0ex}{}{z-r+m-1}{m-1}\right)$ a residue detector modulo $p$, equal to one exactly when $z\equiv r(\mathrm{mod}m)$. Its Boolean evaluation functions have degree at most $m-1$ and a diagonal evaluation matrix on the family. The low-degree evaluation rank on a uniform layer supplies the sharp dimension bound. Without the size qualification, three singletons with $n=3,r=1,m=4$ contradict the customary printed form, since $3>\left(\genfrac{}{}{0ex}{}{3}{3}\right)$.

In the polynomial method in combinatorics, a set family of sets with common size residue $r$ modulo a prime number $p$ annihilates the displayed auxiliary functions. After multilinear reduction on the Boolean cube, functions with $|S|\le s-1$ have degree at most $s$. If $r$ avoids every $j=0,\dots ,s-1$ modulo $p$, these functions are linearly independent: evaluation at a set $T$ gives $(|T|-r){\sum }_{S\subseteq T}{c}_S$, and increasing $|T|$ eliminates coefficients. Combining them with diagonal intersection polynomials removes the lower-degree monomial count and strengthens the dimension bound from ${\sum }_{j\le s}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ to $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$.

Let $p$ be a prime number, $0\le a<p$, $1\le s<p$, and $n\ge a+s$. A multilinear polynomial over ${\mathbb{F}}_p$ of degree less than $s$ that vanishes on every Boolean vertex whose weight is not congruent to $a$ modulo $p$ vanishes everywhere. Alternating sums over intervals of $s$ free coordinates eliminate the possible nonzero weight levels one at a time. This proves independence of the auxiliary functions used for the uniform Frankl-Wilson theorem bound.

Let $p$ be a prime number and $L\subseteq {\mathbb{F}}_p$ have $s$ elements. A set family whose member sizes modulo $p$ avoid $L$, and whose distinct pairwise intersection sizes modulo $p$ belong to $L$, has at most ${\sum }_{j=0}^{\min (s,n)}\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ members. The intersection polynomials ${\prod }_{\ell \in L}({\sum }_{i\in A}{x}_i-\ell )$ have a diagonal, nonzero evaluation matrix on the family's characteristic vectors of sets. Multilinear reduction on the Boolean cube places these linearly independent functions in the space spanned by square-free monomials of degree at most $s$.

If a $k$-uniform set family on an $n$-element ground set has at most $s$ possible intersection sizes between distinct members, then its size is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. The proof uses the linear independence of incidence polynomials on the $k$-slice.

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.