Approximation of Frankl’s conjecture in the complement family

In this paper, we propose an approximation of Frankl’s conjecture in the complement $\mathcal{C}$ of a union-closed family $\mathcal{F}$ in the power set of $U={1,\dotsc, n}$. Frankl’s conjecture is the statement that at least half the members of $\mathcal{F}$ contain some common element $k$ in $U$ and it is equivalent to at most half the members of $\mathcal{C}$ containing some $k$. This paper proves that at most $1/2 + 1/2n$ of the members in $\mathcal{C}$ contain some common element k. In addition, we show that, for arbitrarily small $\epsilon \gt 0$ and any constant $c$ such that $1 \gt c \gt 0$, there is an $N$ such that whenever $\mathcal{F} \subseteq \mathcal{P}(U)$ is a union-closed family of size ${\lvert \mathcal{F} \rvert} \gt c \cdot 2^n$ for some $n \geq N$ then there exists an element that appears in at least $1/2 - \epsilon$ of the member sets.

Keywords

Frankl’s conjecture, union-closed family

2010 Mathematics Subject Classification

05D05

Full Text (PDF format)

Received 15 November 2019

Published 28 December 2022