An upper bound for union-closed family size

2025/11/13 by Bouchard, Christopher · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2511.10608

Abstract

Let A be a union-closed family of sets with universe \bigcup_{A ∈ A}A = [n] = \1,⋯,n\ and length ℓ. We prove that |A| ≤ ∑_i=0^ℓ \binomni, with equality if and only if A = \bigcup_i=0^ℓ\binom[n]n-i. Additionally, by showing that |A| ≤ (ℓ^p-1)/(ℓ-1)+2ⁿ(1-2^-ℓ)^p for any nonnegative integer p, we establish for all integers 1 ≤ k ≤ n that ∑_i=0^k \binomni ≤ \frack^p-1k-1+2ⁿ(1-2^-k)^p, where p=\lfloor (n-k)/log₂(\frack1-2^-k)\rfloor + 1.

Cited by

• Supersaturation in union-closed families of sets

Related

• Minimizing the Number of Unions
• Supersaturation in union-closed families of sets
• An asymptotic version of the union-closed sets conjecture
• A constant lower bound for the union-closed sets conjecture
• Note on the union-closed sets conjecture and Reimer's average set size theorem