Chapter 1 Intersection, Complexity and Correlation
This chapter and the one that follows it focus on the combinatorial properties of collections of subsets of a finite set. Throughout, we let \([n]\) denote the set of the first \(n\) positive integers, i.e.
\begin{equation*}
[n]:=\{1,\dots,n\}\text{.}
\end{equation*}
“Intersection Theorem.”
Given a set \(X\text{,}\) we let \(2^X\) denote the power set of \(X\text{;}\) that is, the collection of all subsets of \(X\text{.}\) In particular,
\begin{equation*}
2^{[n]} = \{A: A\subseteq [n]\}\text{.}
\end{equation*}
The power set of \([n]\) equipped with the partial order \(\subseteq\) is sometimes referred to as the boolean lattice . We consider questions of the following basic form:
How large can a collection \(\mathcal{F}\subseteq 2^{[n]}\) (which we call a family or set system) be, given that it satisfies certain constraints?
Most of this chapter (with the exception of Section 1.4) focuses on extremal properties of set systems whose elements satisfy certain constraints on their intersections with one another.
