A Stability Result for the Union-Closed Size Problem. (18th August 2015) - ECCLES, TOM
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 .