Minimum density of union-closed families

2011/06/02 by Igor Balla, Balla, Igor
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1106.0369

arxiv created 2011/06/02 · arxiv updated 2011/06/03

Abstract

Let F be a finite union-closed family of sets whose largest set contains n elements. In \citeWojcik92, Wojcik defined the density of F to be the ratio of the average set size of F to n and conjectured that the minimum density over all union-closed families whose largest set contains n elements is (1 + o(1))log₂(n)/(2n) as n approaches infinity. We use a result of Reimer \citeReimer03 to show that the density of F is always at least log₂(n)/(2n), verifying Wojcik's conjecture. As a corollary we show that for n ≥ 16, some element must appear in at least √((log₂(n))/n)(|F|/2) sets of F.

Related

• Union-closed families with small average overlap densities
• Note on the union-closed sets conjecture and Reimer's average set size theorem
• Note on the union-closed sets conjecture
• Frequent elements in union-closed set families
• Generalized degrees and densities for families of sets