# Frankl's conjecture and Oeis sequence A188163

For every natural number $c \geq 2$, let $f(c)$ denote the least natural number $f$ with the following property : every union-closed family of sets with at least $f$ members has $c$ members whose intersection is nonempty. If I'm not wrong, it is easy to prove that $f(c)$ always exists. Frankl's conjecture amounts to say that $f(c) \leq 2c-1$.

If $c-1$ is a power of $2$, then $f(c) \geq 2c-1$ (look at the family of all subsets of a set with cardinality $k$, where $c-1 = 2^{k-1}$). Thus, if $c-1$ is a power of $2$, then Frankl's conjecture (if true) is optimal.

But if $c-1$ is not a power of $2$, it can happen that $f(c) < 2c-1$, so that Frankl's conjecture is not optimal in these cases.

For example, if I'm not wrong, $f(4) = 6$ and $f(6) = 10$. So, I searched the Oeis site for a sequence $A$ with the following properties :

$A(1+2^{k-1}) = 1+2^{k}$; $A(4) = 6$; $A(6) = 10$.

1, 3, 5, 6, 9, 10, 11, 13, 17, 18, 19, 20, 22, 23, 25, 28, 33, 34, 35, 36, 37, 39, 40, 41, 43, 44, 46, 49, 50, 52, 55, 59, 65, 66, 67, 68, 69, 70, 72, 73, 74, 75, 77, 78, 79, 81, 82, 84, 87, 88, 89, 91, 92, 94, 97, 98, 100, 103, 107, 108, 110, 113, 117, 122

seems a good candidate, since (numbering $A(n)$from $A(1) = 1$)

$A(3) = 5$, $A(5) = 9$, $A(9) = 17$ and so on, thus $A(1+2^{k-1}) = 1+2^{k}$ in the limits of the table (I don't know if this is always true, I discover this sequence today)

and also $A(4) = 6$; $A(6) = 10$.

(For $c = 1$, we have $f(c) = 2 \neq A(c) = 1$, but it doesn't seem very important to me.)

Is there literature about a possible relation between $f(c)$ and $A188163(c)$ ?

## 1 Answer

Let me elaborate a bit on what I said over at Polymath11.

There is a nice survey on Frankl's conjecture, where the following similar question is discussed in Section 8. Let $\phi:\mathbb{N}\to\mathbb{N}$ be the function where $\phi(n)$ is the smallest maximal abundance of an element of the ground-set of a union-closed family with $n$ members. Frankl's conjecture asserts that $\phi(n)\geq \tfrac{n}{2}$, and computing $\phi(n)$ for small $n$ suggests that $\phi$ may coincide with A004001. The survey notes that this sequence always provides an upper bound for $\phi$, but this upper bound is not always tight and there remains a gap. This has been shown by Renaud.

Concerning your $f$, note that it is by definition the Galois adjoint of $\phi$, $$f(c)\leq n \quad\Leftrightarrow\quad c\leq\phi(n),$$ meaning that $f(c)$ equals the smallest $n$ for which $c\leq \phi(n)$ holds. Since $\phi$ is monotone and surjective, this implies that $f(c)$ is the smallest $n$ for which $\phi(n) = c$ holds; this reflects exactly the relation between A188163 and A004001. Therefore your question is equivalent to asking about the relation between $\phi$ and A004001, which has been answered by Renaud as above.

• For those of us without MathSciNet logins, can you provide a year or partial title for Renaud's work? Gerhard "Not Quite Fully Digitally Connected" Paseman, 2016.03.30. – Gerhard Paseman Mar 30 '16 at 21:16
• The Renaud article is J-C. Renaud, A second approximation to the boundary function on union-closed collections, Ars Combin. 41 (1995), 177–188. – Vince Vatter Mar 30 '16 at 21:27