7.2 Shadows and Compressions

Shadows and compressions are powerful tools in set theory. They help us understand how sets relate to their subsets and how we can transform set systems. These concepts are crucial for solving extremal problems in combinatorics.

The Kruskal-Katona theorem is a key result that uses shadows and compressions. It gives us a lower bound on the size of a set system's shadow, which has many applications in solving combinatorial problems.

Shadows and Compressions in Set Systems

Shadow of set systems

• The shadow of a set system $\mathcal{F}$ on a ground set $[n]$ denoted by $\partial\mathcal{F}$ consists of all sets obtained by removing one element from each set in $\mathcal{F}$
  • Formally, $\partial\mathcal{F} = \{A \subseteq [n] : [|A|](https://www.fiveableKeyTerm:|a|) = k-1 \text{ and } \exists B \in \mathcal{F} \text{ such that } A \subseteq B\}$
  • For example, if $\mathcal{F} = \{\{1,2,3\}, \{2,3,4\}\}$, then $\partial\mathcal{F} = \{\{1,2\}, \{1,3\}, \{2,3\}, \{2,4\}, \{3,4\}\}$
• Properties of the shadow include:
  • If $\mathcal{F}$ is a family of $k$-sets, then $\partial\mathcal{F}$ is a family of $(k-1)$-sets
  • The size of the shadow is at least as large as the size of the original set system ($|\partial\mathcal{F}| \geq |\mathcal{F}|$) because each set in $\mathcal{F}$ has at least one subset in the shadow
  • The shadow operation is monotone, meaning if $\mathcal{F} \subseteq \mathcal{G}$, then $\partial\mathcal{F} \subseteq \partial\mathcal{G}$ ($\mathcal{F}$ being a subset of $\mathcal{G}$ implies the shadow of $\mathcal{F}$ is a subset of the shadow of $\mathcal{G}$)

Compression and shadows

• Compression transforms a set system while preserving or improving certain properties
  • The compression operation on a set system $\mathcal{F}$ with respect to elements $i < j$ denoted by $C_{ij}(\mathcal{F})$ is defined as $C_{ij}(\mathcal{F}) = \{C_{ij}(A) : A \in \mathcal{F}\}$
  • $C_{ij}(A) = \begin{cases} (A \setminus \{j\}) \cup \{i\} & \text{if } j \in A, i \notin A, \text{ and } (A \setminus \{j\}) \cup \{i\} \notin \mathcal{F} \\ A & \text{otherwise} \end{cases}$
  • For example, if $\mathcal{F} = \{\{1,2,4\}, \{2,3,4\}\}$ and we apply $C_{13}$, then $C_{13}(\mathcal{F}) = \{\{1,2,4\}, \{1,2,4\}\} = \{\{1,2,4\}\}$
• Compression does not increase the size of the shadow ($|\partial(C_{ij}(\mathcal{F}))| \leq |\partial\mathcal{F}|$)
• Repeatedly applying compressions to a set system results in a compressed set system with a shadow size no larger than the original set system

Kruskal-Katona theorem proof

• The Kruskal-Katona theorem provides a lower bound on the size of the shadow of a set system
  • Theorem statement: Let $\mathcal{F}$ be a family of $k$-sets on a ground set $[n]$. If $|\mathcal{F}| = \binom{x}{k}$ for some real number $x \geq k$, then $|\partial\mathcal{F}| \geq \binom{x}{k-1}$
• Proof outline using compression:
  1. Start with an arbitrary set system $\mathcal{F}$ of $k$-sets
  2. Apply a sequence of compressions to $\mathcal{F}$ to obtain a compressed set system $\mathcal{F}'$, which has the same size as $\mathcal{F}$ and a shadow size no larger than $\mathcal{F}$
  3. Show that the compressed set system $\mathcal{F}'$ is the collection of the first $|\mathcal{F}|$ $k$-sets in the colex (colexicographic) order
  4. Prove that the shadow of the first $\binom{x}{k}$ $k$-sets in the colex order has size at least $\binom{x}{k-1}$
  5. Conclude that $|\partial\mathcal{F}| \geq |\partial\mathcal{F}'| \geq \binom{x}{k-1}$, providing the desired lower bound on the shadow size

Applications of shadows and compressions

• Solving problems involving shadows and compressions of set systems
  • Example problem: Let $\mathcal{F}$ be a family of $3$-sets on a ground set $[n]$ with $|\mathcal{F}| = 20$. What is the minimum possible size of $\partial\mathcal{F}$?
    1. Find the smallest real number $x \geq 3$ such that $\binom{x}{3} \geq 20$ (by trial and error or using the binomial theorem, $x = 6$)
    2. Apply the Kruskal-Katona theorem with $k = 3$ and $x = 6$, giving $|\partial\mathcal{F}| \geq \binom{6}{2} = 15$
    3. Therefore, the minimum possible size of $\partial\mathcal{F}$ is 15
• Similar problems can be solved by applying the Kruskal-Katona theorem and using the compression technique to analyze the shadow sizes of set systems
  • Other applications include extremal problems in combinatorics, such as the Erdős-Ko-Rado theorem and the Hilton-Milner theorem