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

DOI: http://dx.doi.org/10.4310/JOC.2012.v3.n4.a4

Authors

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.)

Abstract

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.

Keywords

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

2010 Mathematics Subject Classification

05D05

Full Text (PDF format)