Convergence to a fully compressed t-intersecting family
ProvedKatona.exists_compressed_TIntersectingFix a finite ground set , a distinguished element , and a -intersecting family (TIntersecting) of subsets of : every two members, allowing repeats, meet in at least elements. Repeatedly applying the shifting operation (which moves to whenever this is possible without colliding with an existing set) for various can only ever be done finitely many times before no further shift changes anything, because each genuine shift strictly reduces the total weight of the family. This result packages that termination argument together with the fact that shifting preserves both cardinality and the -intersecting property:
Here "stable under " (IsCompressed) means applying the shift to leaves it unchanged. Taking to be the least element of , stability for every is exactly stability under every shift towards , i.e. is fully compressed towards . This reduction — replace an arbitrary -intersecting family by an equally large, fully compressed one — is the first step of Katona's 1964 proof bounding the maximum size of a -intersecting family: once compressed, a family avoiding can be shown to be -intersecting on the remaining elements, which drives an induction on .
Formalization note. The measure used for termination is the standard one from Mathlib's own Kruskal–Katona development (familyMeasure there), specialized here to compressions along singleton sets ; termination is via well-founded recursion on this measure.
import Mathlib import Definitions.Def_TIntersecting open Finset UV open scoped FinsetFamily
namespace Katona
theorem exists_compressed_TIntersecting {n : ℕ} (t : ℕ) (z : Fin n) (𝒜 : Finset (Finset (Fin n)))
(h𝒜 : TIntersecting t 𝒜) :
∃ ℬ : Finset (Finset (Fin n)), 𝒜.card = ℬ.card ∧ TIntersecting t ℬ ∧
∀ i : Fin n, (z : ℕ) < (i : ℕ) →
IsCompressed ({z} : Finset (Fin n)) ({i} : Finset (Fin n)) ℬ := by sorry
end Katona