Journal of Combinatorics

Volume 3 (2012)

Number 4

An extremal problem for set families generated with the union and symmetric difference operations

Pages: 651 – 668



Yuejian Peng (School of Mathematics, Hunan University, Changsha, China)

Papa Sissokho (Mathematics Department, Illinois State University, Normal, Il., U.S.A.)

Cheng Zhao (Department of Mathematics and Computer Science, Indiana State University, Terre Haute, In., U.S.A.)


Let ${\mathcal G}$ be a family of sets and let ${\cup}^{n}{\mathcal G}$ be the family of sets obtained by taking all unions of $k$ sets of ${\mathcal G}$ with $1\leq k\leq n$. We define the $\textit{half-life}$ of ${\mathcal G}$ with respect to the union operation, denoted by $h_{\cup}({\mathcal G})$, to be the smallest integer $n$ such that some $x\in\cup_{A\in{\mathcal G}}A$ appears in at least half of the sets in ${\cup}^{n}{\mathcal G}$. If no such $n$ exists, then we define it as $\infty$. We also define the half-life of ${\mathcal G}$ with respect to the symmetric difference operation in a similar fashion and denote it by $h_{\Delta}({\mathcal G})$. In this paper, we establish several bounds for $h_{\cup}({\mathcal G})$ and $h_{\Delta}({\mathcal G})$. As a byproduct, we confirm Fránkl’s union-closed conjecture for some special cases.


union-closed sets, union-closed conjecture, half-life

2010 Mathematics Subject Classification


Full Text (PDF format)