UV-compression preserves t-intersecting families
ProvedKatona.compression_preserves_TIntersectingFix a finite ground set and two distinct elements . Recall the classical shifting (or compression) operation on subsets of : it replaces by in any set that contains but not , and leaves every other set unchanged. Applying to a family produces a new family of the same cardinality (a set already carrying its own shifted image simply stays put, so nothing is identified or lost).
Let be a -intersecting family (TIntersecting): every pair of members , allowing , satisfies . This result shows that shifting preserves this property:
This is the non-uniform generalization of the classical fact, used throughout extremal set theory (starting with the shifting technique in Erdős–Ko–Rado-type arguments), that the shifting operation preserves the (ordinary, ) intersecting property. Iterating over all therefore lets one replace an arbitrary -intersecting family by one that is compressed toward without changing its size or its -intersecting property — the key reduction step in Katona's 1964 proof of the maximum size of a -intersecting family.
Formalization note. The shift is Mathlib's general UV.compress operator specialized to the singletons , and is its family-level lift UV.compression (notation 𝓒), already used in Mathlib's proof of the Kruskal–Katona theorem.
import Mathlib import Definitions.Def_TIntersecting open Finset UV open scoped FinsetFamily
namespace Katona
theorem compression_preserves_TIntersecting {n : ℕ} (z i : Fin n) (hzi : z ≠ i) (t : ℕ)
{𝒜 : Finset (Finset (Fin n))} (h𝒜 : TIntersecting t 𝒜) :
TIntersecting t (𝓒 ({z} : Finset (Fin n)) ({i} : Finset (Fin n)) 𝒜) := by sorry
end Katona