7.3 Applications in Extremal Set Theory

The Kruskal-Katona theorem is a powerful tool in extremal set theory. It provides a lower bound on the size of a set system's shadow, which is crucial for proving various results about maximum set sizes and specific characteristics.

This theorem plays a key role in proving the Erdős-Ko-Rado theorem on intersecting families. It's also used to derive bounds on set systems with different properties, making it essential for solving many extremal problems in set theory.

Kruskal-Katona Theorem and Its Applications

Application of Kruskal-Katona theorem

• Provides lower bound on size of shadow of set system
  • Shadow of set system $\mathcal{A} \subseteq \binom{[n]}{k}$ defined as $\partial \mathcal{A} = \{B \in \binom{[n]}{k-1} : \exists A \in \mathcal{A} \text{ such that } B \subseteq A\}$
  • Theorem states for any set system $\mathcal{A} \subseteq \binom{[n]}{k}$, $|\partial \mathcal{A}| \geq \binom{x}{k-1}$, where $x$ is unique real number satisfying $|\mathcal{A}| = \binom{x}{k}$
• Proves various results in extremal set theory
  • Determines maximum size of set system with given property (minimum degree)
  • Establishes existence of set systems with specific characteristics (matching number)

Kruskal-Katona vs Erdős-Ko-Rado theorems

• Erdős-Ko-Rado theorem fundamental result concerning intersecting families
  • Intersecting family collection of sets where any two sets have non-empty intersection
  • Theorem states for $n \geq 2k$, maximum size of intersecting family $\mathcal{A} \subseteq \binom{[n]}{k}$ is $\binom{n-1}{k-1}$
• Kruskal-Katona theorem used to prove Erdős-Ko-Rado theorem
  • Applying Kruskal-Katona theorem to shadow of intersecting family derives upper bound on size of family
  • Highlights importance of Kruskal-Katona theorem in study of intersecting families and other extremal problems

Bounds from Kruskal-Katona theorem

• Derives bounds on size of set systems with various properties
  • Bounds size of set system with given minimum degree
    • Degree of set $A$ in set system $\mathcal{A}$ is number of sets in $\mathcal{A}$ that contain $A$
  • Bounds size of set system with given matching number
    • Matching in set system is collection of pairwise disjoint sets
    • Matching number is maximum size of matching in set system
• Applies Kruskal-Katona theorem to shadow of set system and exploits specific properties of system to derive tight bounds on its size

Role in extremal problems

• Powerful tool in study of intersecting families and other extremal problems in set theory
  • Proves various results concerning maximum size of intersecting families
  • Studies structure of intersecting families and characterizes extremal examples (Erdős-Ko-Rado theorem)
• Applications in other areas of extremal set theory
  • Studies t-intersecting families where any two sets have at least t elements in common
  • Investigates cross-intersecting families with two families of sets where any set from one family intersects any set from the other family
• Derives bounds and characterizes extremal examples in related problems