Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

UV-compression preserves t-intersecting families

Proved
Katona.compression_preserves_TIntersecting

by xbgxjack · Sep 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricscompressionextremal-set-theorykatonashifting

Fix a finite ground set [n]={0,…,n−1}[n] = \{0, \dots, n-1\}[n]={0,…,n−1} and two distinct elements z,i∈[n]z, i \in [n]z,i∈[n]. Recall the classical shifting (or compression) operation Sz,iS_{z,i}Sz,i​ on subsets of [n][n][n]: it replaces iii by zzz in any set that contains iii but not zzz, and leaves every other set unchanged. Applying Sz,iS_{z,i}Sz,i​ to a family A\mathcal{A}A produces a new family Sz,i(A)S_{z,i}(\mathcal{A})Sz,i​(A) of the same cardinality (a set already carrying its own shifted image simply stays put, so nothing is identified or lost).

Let A\mathcal{A}A be a ttt-intersecting family (TIntersecting): every pair of members A,B∈AA, B \in \mathcal{A}A,B∈A, allowing A=BA = BA=B, satisfies ∣A∩B∣≥t|A \cap B| \ge t∣A∩B∣≥t. This result shows that shifting preserves this property:

A is t-intersecting  ⟹  Sz,i(A) is t-intersecting.\mathcal{A} \text{ is } t\text{-intersecting} \implies S_{z,i}(\mathcal{A}) \text{ is } t\text{-intersecting}.A is t-intersecting⟹Sz,i​(A) is t-intersecting.

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, t=1t=1t=1) intersecting property. Iterating Sz,iS_{z,i}Sz,i​ over all i≠zi \ne zi=z therefore lets one replace an arbitrary ttt-intersecting family by one that is compressed toward zzz without changing its size or its ttt-intersecting property — the key reduction step in Katona's 1964 proof of the maximum size of a ttt-intersecting family.

Formalization note. The shift Sz,iS_{z,i}Sz,i​ is Mathlib's general UV.compress operator specialized to the singletons {z},{i}\{z\}, \{i\}{z},{i}, and Sz,i(A)S_{z,i}(\mathcal{A})Sz,i​(A) is its family-level lift UV.compression (notation 𝓒), already used in Mathlib's proof of the Kruskal–Katona theorem.

Preamble
import Mathlib
import Definitions.Def_TIntersecting

open Finset UV
open scoped FinsetFamily
Formal statement
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
Source
Classical shifting technique, e.g. as used in Katona's proof of his 1964 intersection theorem (G. O. H. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329-337) and the standard shifting proof of the Erdős-Ko-Rado theorem.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me