Skip to main content

Math 426/529: Extremal Combinatorics

Jonathan A. Noel

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*}
🔗
described in detail following the image
“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.
🔗
🔗
PrevTopNext