Set family

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.