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 's , which has many applications in solving combinatorial problems.
Shadows and Compressions in Set Systems
Shadow of set systems
The shadow of a set system F on a ground set [n] denoted by ∂F consists of all sets obtained by removing one element from each set in F
Formally, ∂F={A⊆[n]:[∣A∣](https://www.fiveableKeyTerm:∣a∣)=k−1 and ∃B∈F such that A⊆B}
For example, if F={{1,2,3},{2,3,4}}, then ∂F={{1,2},{1,3},{2,3},{2,4},{3,4}}
Properties of the shadow include:
If F is a family of k-sets, then ∂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 (∣∂F∣≥∣F∣) because each set in F has at least one subset in the shadow
The shadow operation is , meaning if F⊆G, then ∂F⊆∂G (F being a subset of G implies the shadow of F is a subset of the shadow of G)
Compression and shadows
transforms a set system while preserving or improving certain properties
The compression operation on a set system F with respect to elements i<j denoted by Cij(F) is defined as Cij(F)={Cij(A):A∈F}
Cij(A)={(A∖{j})∪{i}Aif j∈A,i∈/A, and (A∖{j})∪{i}∈/Fotherwise
For example, if F={{1,2,4},{2,3,4}} and we apply C13, then C13(F)={{1,2,4},{1,2,4}}={{1,2,4}}
Compression does not increase the size of the shadow (∣∂(Cij(F))∣≤∣∂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 F be a family of k-sets on a ground set [n]. If ∣F∣=(kx) for some real number x≥k, then ∣∂F∣≥(k−1x)
Proof outline using compression:
Start with an arbitrary set system F of k-sets
Apply a sequence of compressions to F to obtain a compressed set system F′, which has the same size as F and a shadow size no larger than F
Show that the compressed set system F′ is the collection of the first ∣F∣k-sets in the colex (colexicographic) order
Prove that the shadow of the first (kx)k-sets in the colex order has size at least (k−1x)
Conclude that ∣∂F∣≥∣∂F′∣≥(k−1x), 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 F be a family of 3-sets on a ground set [n] with ∣F∣=20. What is the minimum possible size of ∂F?
Find the smallest real number x≥3 such that (3x)≥20 (by trial and error or using the binomial theorem, x=6)
Apply the Kruskal-Katona theorem with k=3 and x=6, giving ∣∂F∣≥(26)=15
Therefore, the minimum possible size of ∂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 and the