a note on the union-closed sets conjecture
Ian T. Roberts, Jamie Simpson · CDU eSpace Institutional Repository (Charles Darwin University) · 2010
A collection A of finite sets is closed under union if A, B ∈ A implies that A ∪ B ∈ A. The Union-Closed Sets Conjecture states that if A is a union-closed collection of sets, containing at least one non-empty set, then there is an element which belongs to at least half of the sets in A. We show that if q is the minimum cardinality of ∪A taken over all counterexamples A, then any counterexample A has cardinality at least 4q -1.A collection A of finite sets is closed under union if A, B ∈ A implies that A ∪ B ∈ A. The Union-Closed Sets Conjecture (also called Frankl's Conjecture) states that if A is a union-closed collection of sets, containing at least one nonempty set, then there is an element which belongs to at least half of the sets in A. The conjecture dates from 1979 and is generally attributed to Peter Frankl [2].Some authors place the further condition on A that it does not contain the empty set.The results of this note apply to either version of the conjecture.A number of necessary conditions for a counterexample have been established, including that if A is a counterexample then |A| ≥ 37 [4] and that | ∪ A| ≥ 12 [1] where ∪A = ∪ A∈A A. See [1] and [3] and their bibliographies for more background.In this note we show that if q is the minimum cardinality of ∪A taken over all counterexamples then for any counterexample A we have |A| ≥ 4q -1.It is known that q ≥ 12 [1] so this implies that a counterexample has cardinality at least 47.