On union-closed families. I (Q5906309)

From MaRDI portal
scientific article; zbMATH DE number 1236154
Language Label Description Also known as
English
On union-closed families. I
scientific article; zbMATH DE number 1236154

    Statements

    On union-closed families. I (English)
    0 references
    0 references
    0 references
    2 August 1999
    0 references
    A family \(F\) of sets is called a UC-family if \(X\cup Y\in F\) whenever \(X\) and \(Y\) belong to \(F\). If, in addition, all the members of \(F\) are finite and non-empty, \(F\) is not a chain, the maximal element \(S\) of \(F\) is the union of \(F\setminus\{S\}\), and \(F\) has at least two minimal elements then \(F\) is said to be a \(\text{UC}^*\)-family. Let \(\text{MGS}(F)\) be the family of members of \(F\) which cover (in the poset of members of \(F\), ordered by inclusion) at most one element. Let \(F\) be a \(\text{UC}^*\)-family with maximal element \(S\) and with \(\text{MGS}(F)=\{A_1, \dots, A_n\}\). The dual \(F^*\) of \(F\) is defined to be the smallest UC-family of subsets of \(\{1, \dots,n\}\) which contains all sets \(\{i\mid x\in A_i\}\), where \(x\in S\). The authors prove the following result: Let \(F\) be a \(\text{UC}^*\)-family. Then there exists some \(x\) contained in at least half the members of \(F\) or there exists some \(i\) contained in at least half the members of \(F^*\). See also the review below.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    union-closed family
    0 references
    Frankl's conjecture
    0 references
    dual family
    0 references
    minimum generating set
    0 references
    0 references
    0 references
    0 references
    0 references