Extremal set theory

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

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$.

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

IfthenInitial segments of colexicographic order attain equality.

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.

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$.

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

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.

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.

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}$.

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.

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

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.