Union-closed families of sets

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Balla, Igor^1,2  Bollobas, Bela^1,2  Eccles, Tom¹ 

[1] Dept Pure Math & Math Stat, Cambridge CB3 0WB, England

[2] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

关键词: Union-closed;    Average size;    Compressions;   

DOI  :  10.1016/j.jcta.2012.10.005

来源: Elsevier

【 摘 要 】

of its elements. Reimer (2003) [16] and Czedli (2009) [2] investigated the average size of an element of a union-closed family consisting of m subsets of a ground set with n elements. We determine the minimum average size precisely, verifying a conjecture of Czedli, Maroti and Schmidt (2009) [3]. As a consequence, the union-closed conjecture holds if m >= 2/3.2(n) - in this case some element of [n] is in at least half the sets of the family. (c) 2012 Elsevier Inc. All rights reserved.

【 授权许可】

Free