← All papers
On the Averaging Problem of Ideal Families Related to Frankl's Conjecture with Formal Proof by Lean 4
math.CO
Apr 18, 2025 · v1
TL;DR
Formalizes and verifies in Lean 4 that every ideal set family satisfies the average rarity condition related to Frankl's conjecture.
Abstract
Frankl's conjecture, also known as the union-closed sets conjecture, can be equivalently expressed in terms of intersection-closed set families by considering the complements of sets. It posits that any family of sets closed under intersections, and containing both the ground set and the empty set, must have a ``rare vertex'' -- a vertex belonging to at most half of the members of the family. The concept of \emph{average rarity} describes a set family where the average degree of all the elements is at most half of the number of its members. Average rarity is a stronger property that implies the existence of a rare vertex. This paper focuses on ideal families, which are set families that are downward-closed (except the ground set) and include the ground set. We present a proof that the normalized degree sum of any ideal family is non-positive, which is equivalent to saying that every ideal family satisfies the average rarity condition. This proof is formalized and verified using the Lean 4 theorem prover.
Problem
Frankl's conjecture (union-closed sets conjecture) asks whether every such family has a rare vertex. Whether all ideal families (downward-closed families including the ground set) satisfy the stronger average-rarity condition was an open question.
Approach
The authors prove that the normalized degree sum of any ideal family is nonpositive, equivalent to showing every ideal family satisfies the average-rarity condition. The proof is formalized and verified in Lean 4.
Results
The average-rarity property is established for all ideal families, providing a formally verified partial result toward Frankl's conjecture.
