7
$\begingroup$

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

A188163 ( http://oeis.org/search?q=3%2C5%2C6%2C9%2C10&language=english&go=Search) :

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)$ ?

$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Mar 30 '16 at 21:16
  • 1
    $\begingroup$ The Renaud article is J-C. Renaud, A second approximation to the boundary function on union-closed collections, Ars Combin. 41 (1995), 177–188. $\endgroup$ – Vince Vatter Mar 30 '16 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.