The Union-Closed Set Conjecture Is True

Abstract

Roberto Demontis

We prove that the conjecture made by Peter Frankl in the late 1970s is true. In other words, for every finite union-closed family which contains a nonempty set, there is an element that belongs to at least half of its members. The union-closed set conjecture is one of the most famous combinatorial problems. It asserts that for every finite union-closed family which contains a non-empty set, there is an element that belongs to at least half of its members. In literature, there have been several partial results regarding this, as can be seen from the survey paper of Bruhn and Schaudt. For instance, in V. B. Alekseev approximates the number of union-closed families of subset of [n]. In I. Ballad , B. Bolloba`s and T. Eccles prove that the conjecture occurs for union-closed families with more sets compared to the size of the universe, this size has been further improved by Eccles in [1-5]. On the other hand, in I. Bo�?snjak and P. Markova’s show that the conjecture is true for any-closed family with a universe of 11 elements. Moreover in V. Flag-Waver proves that if a union-closed set 2 with a universe of n elements contains at most 2n element with the property to be separated, then the conjecture holds. Moreover in J. Mossberg reinforces the latter result. First of all, we introduce some preliminary terminology and notation according to the literature [6-8].

We call A = 2 [n] −{∅}. We will use uppercase letters for elements of A, lowercase letters for elements of ∪A, mathcal character uppercase letters for subsets of A. Let F ⊆ A union-closed if for all X, Y ∈ F, X ∪ Y ∈ F. For all i ≤ n we say F i = {X ∈ F: i ∈ X}. We note |A| = 2 n − 1 and |A i | = 2 n−1 . The purpose of this paper is to prove

PDF