Journal of Combinatorics

Volume 14 (2023)

Number 3

Approximation of Frankl’s conjecture in the complement family

Pages: 399 – 403

DOI: https://dx.doi.org/10.4310/JOC.2023.v14.n3.a5

Author

Yasuo Nishii (University of Tsukuba, Tsukuba-shi, Ibaraki, Japan)

Abstract

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

The full text of this article is unavailable through your IP address: 44.210.77.73

Received 15 November 2019

Published 28 December 2022