Extremal Set Systems

Extremal combinatorics studies how large or small a collection of combinatorial structures can be, given certain constraints. The theory of extremal set systems investigates the maximum size of families of subsets satisfying prescribed intersection or containment conditions.

Fundamental Definitions

Definition4.1Sunflower (Delta-System)

A family $\mathcal{F} = \{F_1, F_2, \ldots, F_k\}$ of sets is called a sunflower (or $\Delta$ -system) with core $Y$ if $F_i \cap F_j = Y$ for all $i \neq j$ . The sets $F_i \setminus Y$ are called the petals and must be pairwise disjoint and non-empty.

Definition4.2Antichain and Sperner Family

A family $\mathcal{F} \subseteq 2^{[n]}$ is called an antichain (or Sperner family) if no member of $\mathcal{F}$ is contained in another, i.e., for all $A, B \in \mathcal{F}$ with $A \neq B$ , we have $A \not\subseteq B$ and $B \not\subseteq A$ .

The maximum size of an antichain in $2^{[n]}$ is $\binom{n}{\lfloor n/2 \rfloor}$ , achieved by taking all subsets of size $\lfloor n/2 \rfloor$ .

Intersection Properties

Definition4.3Intersecting Family

A family $\mathcal{F} \subseteq \binom{[n]}{k}$ is called intersecting if $A \cap B \neq \emptyset$ for all $A, B \in \mathcal{F}$ . More generally, $\mathcal{F}$ is $t$ -intersecting if $|A \cap B| \geq t$ for all $A, B \in \mathcal{F}$ .

ExampleStar Construction

For any fixed element $x \in [n]$ , the family $\mathcal{F}_x = \{A \in \binom{[n]}{k} : x \in A\}$ is intersecting and has size $\binom{n-1}{k-1}$ . This is called a star or principal intersecting family centered at $x$ .

RemarkShifting Technique

The shifting (or compression) operation is a fundamental tool in extremal set theory. For $i < j$ , the $(i,j)$ -shift of a family $\mathcal{F}$ replaces each set $A \in \mathcal{F}$ containing $j$ but not $i$ by $(A \setminus \{j\}) \cup \{i\}$ , provided the resulting set is not already in $\mathcal{F}$ . Shifting preserves the size of $\mathcal{F}$ and the intersecting property, while producing a "simpler" family.

Shadows and Kruskal-Katona Theory

Definition4.4Shadow of a Family

For a family $\mathcal{F} \subseteq \binom{[n]}{k}$ , the shadow of $\mathcal{F}$ is $\partial \mathcal{F} = \left\{ G \in \binom{[n]}{k-1} : G \subseteq F \text{ for some } F \in \mathcal{F} \right\}.$ The upper shadow is similarly $\partial^+ \mathcal{F} = \{G \in \binom{[n]}{k+1} : F \subseteq G \text{ for some } F \in \mathcal{F}\}$ .

The Kruskal-Katona theorem determines the minimum possible shadow size for a family of given cardinality: the initial segment in the colex order minimizes the shadow among all families of the same size.

ExampleShadow of a Triangle Family

Let $\mathcal{F} = \{\{1,2,3\}, \{1,2,4\}, \{1,3,4\}\} \subseteq \binom{[4]}{3}$ . Then the shadow is $\partial \mathcal{F} = \{\{1,2\}, \{1,3\}, \{2,3\}, \{1,4\}, \{2,4\}, \{3,4\}\} = \binom{[4]}{2},$ so $|\partial \mathcal{F}| = 6$ .