Inequalities for cross-unions of collections of finite sets

Uwe Leck, Ian Roberts

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    Some inequalities for cross-unions of families of finite sets are proved that are related to the problem of minimizing the union-closure of a uniform family of given size. The cross-union of two families F and G of subsets of [n]={1,2,…,n}[n]={1,2,…,n} is the family F∨G={F∪G:F∈F,G∈G}. It is shown that |F∨G|/|F|≥|G∨Bn|/2n|, where Bn denotes the power set of [n]. Besides, the problem of minimizing |F∨G|over all union-closed FF and G∨G generated by a given number r of singletons and a given number s > (r 2)  of two-sets, respectively, is solved.
    Original languageEnglish
    Pages (from-to)392-401
    Number of pages10
    JournalEuropean Journal of Combinatorics
    Volume35
    DOIs
    Publication statusPublished - 2014

    Fingerprint

    Finite Set
    Union
    Power set
    Closure
    Closed
    Subset
    Family

    Cite this

    Leck, Uwe ; Roberts, Ian. / Inequalities for cross-unions of collections of finite sets. In: European Journal of Combinatorics. 2014 ; Vol. 35. pp. 392-401.
    @article{45594bdc71114f7a899ceea88a00d761,
    title = "Inequalities for cross-unions of collections of finite sets",
    abstract = "Some inequalities for cross-unions of families of finite sets are proved that are related to the problem of minimizing the union-closure of a uniform family of given size. The cross-union of two families F and G of subsets of [n]={1,2,…,n}[n]={1,2,…,n} is the family F∨G={F∪G:F∈F,G∈G}. It is shown that |F∨G|/|F|≥|G∨Bn|/2n|, where Bn denotes the power set of [n]. Besides, the problem of minimizing |F∨G|over all union-closed FF and G∨G generated by a given number r of singletons and a given number s > (r 2)  of two-sets, respectively, is solved.",
    author = "Uwe Leck and Ian Roberts",
    year = "2014",
    doi = "10.1016/j.ejc.2013.06.036",
    language = "English",
    volume = "35",
    pages = "392--401",
    journal = "European Journal of Combinatorics",
    issn = "0195-6698",
    publisher = "Academic Press",

    }

    Inequalities for cross-unions of collections of finite sets. / Leck, Uwe; Roberts, Ian.

    In: European Journal of Combinatorics, Vol. 35, 2014, p. 392-401.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Inequalities for cross-unions of collections of finite sets

    AU - Leck, Uwe

    AU - Roberts, Ian

    PY - 2014

    Y1 - 2014

    N2 - Some inequalities for cross-unions of families of finite sets are proved that are related to the problem of minimizing the union-closure of a uniform family of given size. The cross-union of two families F and G of subsets of [n]={1,2,…,n}[n]={1,2,…,n} is the family F∨G={F∪G:F∈F,G∈G}. It is shown that |F∨G|/|F|≥|G∨Bn|/2n|, where Bn denotes the power set of [n]. Besides, the problem of minimizing |F∨G|over all union-closed FF and G∨G generated by a given number r of singletons and a given number s > (r 2)  of two-sets, respectively, is solved.

    AB - Some inequalities for cross-unions of families of finite sets are proved that are related to the problem of minimizing the union-closure of a uniform family of given size. The cross-union of two families F and G of subsets of [n]={1,2,…,n}[n]={1,2,…,n} is the family F∨G={F∪G:F∈F,G∈G}. It is shown that |F∨G|/|F|≥|G∨Bn|/2n|, where Bn denotes the power set of [n]. Besides, the problem of minimizing |F∨G|over all union-closed FF and G∨G generated by a given number r of singletons and a given number s > (r 2)  of two-sets, respectively, is solved.

    U2 - 10.1016/j.ejc.2013.06.036

    DO - 10.1016/j.ejc.2013.06.036

    M3 - Article

    VL - 35

    SP - 392

    EP - 401

    JO - European Journal of Combinatorics

    JF - European Journal of Combinatorics

    SN - 0195-6698

    ER -