7.1 Kruskal-Katona Theorem and its Proof

The Kruskal-Katona theorem is a powerful tool in extremal combinatorics. It provides a lower bound on the size of a set system's shadow, helping us understand the structure and properties of these systems.

This theorem has wide-ranging applications in combinatorics. It's used to solve problems involving set systems, prove lower bounds, and tackle extremal problems like the Erdős-Ko-Rado theorem. Its generalization, the Lovász version, extends these applications even further.

Kruskal-Katona Theorem

Kruskal-Katona theorem and implications

Top images from around the web for Kruskal-Katona theorem and implications

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Hypergraph - Wikipedia View original

  Is this image relevant?

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Hypergraph - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Kruskal-Katona theorem and implications

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Hypergraph - Wikipedia View original

  Is this image relevant?

• 

  Axiom of power set - Wikipedia View original

  Is this image relevant?

• 

  Hypergraph - Wikipedia View original

  Is this image relevant?

1 of 2

• Provides a lower bound on the size of the shadow of a 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\}$ contains all subsets of size $k-1$ that are contained in at least one set in $\mathcal{A}$
• Theorem states for any set system $\mathcal{A} \subseteq \binom{[n]}{k}$, $|\partial \mathcal{A}| \geq |\partial C_{|\mathcal{A}|,k}|$
  • $C_{|\mathcal{A}|,k}$ represents the colexicographically first $|\mathcal{A}|$ sets in $\binom{[n]}{k}$ ($k$-subsets of $[n]$ ordered colexicographically)
• Implications for set systems:
  • Provides a tight lower bound on the shadow size
  • Helps understand structure and properties of set systems ($k$-uniform hypergraphs)
  • Useful in solving combinatorial problems involving set systems (extremal hypergraph theory, coding theory)

Proof of Kruskal-Katona theorem

• Shifting technique is a powerful tool used to prove the theorem
• For a set $A \subseteq [n]$ and $i < j \in [n]$, the $(i,j)$-shift of $A$ defined as:
  • $S_{i,j}(A) = (A \setminus \{j\}) \cup \{i\}$ if $j \in A, i \notin A$, and $(A \setminus \{j\}) \cup \{i\} \notin \mathcal{A}$ (replaces $j$ with $i$ if the resulting set is not already in $\mathcal{A}$)
  • $S_{i,j}(A) = A$ otherwise (no change if conditions not met)
• For a set system $\mathcal{A}$, the $(i,j)$-shift defined as $S_{i,j}(\mathcal{A}) = \{S_{i,j}(A) : A \in \mathcal{A}\} \cup \{A \in \mathcal{A} : S_{i,j}(A) = A\}$ (applies shift to each set in $\mathcal{A}$ and includes sets that remain unchanged)
• Key properties of shifting:
  • Preserves the size of the set system: $|S_{i,j}(\mathcal{A})| = |\mathcal{A}|$
  • Does not increase the shadow size: $|\partial S_{i,j}(\mathcal{A})| \leq |\partial \mathcal{A}|$
• Proof steps:
  1. Start with an arbitrary set system $\mathcal{A} \subseteq \binom{[n]}{k}$
  2. Repeatedly apply shifting until no further shifts are possible, resulting in a shifted set system $\mathcal{A}^*$
  3. Prove $\mathcal{A}^*$ is colexicographically first, i.e., $\mathcal{A}^* = C_{|\mathcal{A}|,k}$ (can be shown by contradiction)
  4. Since shifting does not increase shadow size, $|\partial \mathcal{A}| \geq |\partial \mathcal{A}^*| = |\partial C_{|\mathcal{A}|,k}|$, proving the theorem

Applications of Kruskal-Katona theorem

• Can be applied to solve various problems involving set systems:
  • Determining minimum shadow size given set system size and uniform rank ($k$)
  • Proving lower bounds on sizes of set systems with certain properties (intersecting families, $t$-intersecting families)
  • Solving extremal problems in combinatorics (Erdős-Ko-Rado theorem, Hilton-Milner theorem)
• Example application: Prove for any set system $\mathcal{A} \subseteq \binom{[n]}{k}$ with $|\mathcal{A}| > \binom{n-1}{k-1}$, there exist two sets $A, B \in \mathcal{A}$ such that $|A \cap B| = k-1$
  • Proof:
    1. Suppose $|\mathcal{A}| > \binom{n-1}{k-1}$
    2. By Kruskal-Katona theorem, $|\partial \mathcal{A}| \geq |\partial C_{|\mathcal{A}|,k}|$
    3. $C_{|\mathcal{A}|,k}$ contains all $k$-sets from $[n-1]$ and some $k$-sets containing element $n$
    4. Therefore, $|\partial C_{|\mathcal{A}|,k}| > \binom{n-1}{k-1}$, implying existence of two sets in $\mathcal{A}$ with intersection size $k-1$ (pigeonhole principle)

Kruskal-Katona vs Lovász theorem

• Lovász version is a generalization of the original Kruskal-Katona theorem
• Kruskal-Katona theorem deals with shadow size, while Lovász version considers $d$-shadow size
  • $d$-shadow of set system $\mathcal{A} \subseteq \binom{[n]}{k}$ defined as $\partial^d \mathcal{A} = \{B \in \binom{[n]}{k-d} : \exists A \in \mathcal{A} \text{ such that } B \subseteq A\}$ (subsets of size $k-d$ contained in at least one set in $\mathcal{A}$)
• Lovász version states for any set system $\mathcal{A} \subseteq \binom{[n]}{k}$, $|\partial^d \mathcal{A}| \geq |\partial^d C_{|\mathcal{A}|,k}|$
• Original Kruskal-Katona theorem is a special case of Lovász version when $d = 1$
• Proof of Lovász version follows similar approach using shifting technique
• Lovász version provides more general lower bound on $d$-shadow size, useful in solving wider range of combinatorial problems (Erdős matching conjecture, Erdős-Frankl conjecture)