A Stability Result for the Union-Closed Size Problem. (18th August 2015)

• Record Type: Journal Article
• Authors: ECCLES, TOM
• Is Part Of: Combinatorics, probability and computing. Volume 25:Number 3(2016:May)
• Page Start: 399
• Page End: 418
• Publication Date: 2015-08-18
• Subjects: Primary 05A18, -- Secondary 05D05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548315000176
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : A family of sets is called union-closed if whenever A and B are sets of the family, so is A ∪ B . The long-standing union-closed conjecture states that if a family of subsets of [ n ] is union-closed, some element appears in at least half the sets of the family. A natural weakening is that the union-closed conjecture holds for large families, that is, families consisting of at least p 0 2 n sets for some constant p 0 . The first result in this direction appears in a recent paper of Balla, Bollobás and Eccles [1 ], who showed that union-closed families of at least $\tfrac{2}{3}$ 2 n sets satisfy the conjecture; they proved this by determining the minimum possible average size of a set in a union-closed family of given size. However, the methods used in that paper cannot prove a better constant than $\tfrac{2}{3}$ . Here, we provide a stability result for the main theorem of [1 ], and as a consequence we prove the union-closed conjecture for families of at least ( $\tfrac{2}{3}$ − c )2 n sets, for a positive constant c .