7
$\begingroup$

If I'm not wrong, it is easy to prove the following statements :

1° For every natural number $k$, every union-closed family that has at least $2$ members with cardinality $\geq k$ has at least $2$ members whose intersection has cardinality $\geq k$. This is trivial : if $X$and $Y$ are two distinct members of the family with cardinality $\geq k$, we can assume that $Y$ is not contained in $X$. Then $X$ and $X \cup Y$ are two distinct members of the family whose intersection is $X$ and has thus cardinality $\geq k$.

2° For every natural number $k$, every union-closed family that has at least $k+3$ members with cardinality $\geq k$ has at least $3$ members whose intersection has cardinality $\geq k$.

3° For every natural number $k$, every union-closed family that has at least $k+4$ members with cardinality $\geq k$ has at least $4$ members whose intersection has cardinality $\geq k$.

I think I have also a proof of the following statement :

4° For every natural number $k$, every union-closed family that has at least $\frac{k^{2}+5k}{2} + 5$ members with cardinality $\geq k$ has at least $5$ members whose intersection has cardinality $\geq k$.

My question is : are there results such as : "If a union-closed family of sets has at least this number of members with cardinalty $\geq k$, then the family has at least $c$ members whose intersection has cardinality $\geq k$".

(Edit :) For every natural number $c \geq 1$ and for every natural number $k \geq 0$, let $s(c,k)$ denote the least natural number $s$ with the following property : every union-closed family that has at least $s$ members with cardinality $\geq k$ has at least $c$ members whose intersection has cardinality $\geq k$. (I presume that such an $s$ always exists, so that $s(c,k)$ always exists.) Clearly, $s(1,k) = 1$ and the above statements amount to say that $s(2,k) \leq 2$, $s(3,k) \leq k + 3$, $s(4,k) \leq k + 4$, $s(5,k) \leq \frac{k^{2}+5k}{2} + 5$. In fact, it is easy to find examples proving that $s(2,k) = 2$, $s(3,k) = k + 3$, $s(4,k) = k + 4$, $s(5,k) = \frac{k^{2}+5k}{2} + 5$.

(In order to prove that $s(5,k) \geq \frac{k^{2}+5k}{2} + 5$, look at the family of all subsets of a set with cardinality $k+2$.)

Thus, it seems reasonable to conjecture that for every natural number $c \geq 1$, there is a polynomial $f_{c}(X)$ such that for every natural number $k$, $s(c,k) = f_{c}(k)$.

The first poynomials of the sequence are $f_{1}(X) = 1$, $f_{2}(X) = 2$, $f_{3}(X) = X+3$, $f_{4}(X) = X+4$, $f_{5}(X) = \frac{X^{2}+5X}{2} + 5$.

Is there a known sequence of polynomials beginning in this manner ?

Note : for every natural number $r \geq 0$, we must have

$s(1 + 2^{r}, k) \geq {k+r \choose k} + {k+r \choose k+1} + \ldots + {k+r \choose k+r} +1$.

(Look at the family of all subsets of a set with $k+r$ elements.)

In the limits of the above results, $s(1 + 2^{r}, k)$ is equal to the found minimal value, $s(c, k)$ grows unit by unit when $c$ runs from $c = 1 + 2^{r}$ to $c=2^{r+1}$ (included) and, for $c=1+2^{r+1}$, takes again the found minimal value (with $r+1$ instead of $r$).

$\endgroup$
2
  • 2
    $\begingroup$ I was going to mention the current Polymath project hosted on Gowers's blog, but I see from your previous question that you already know about it. You might find a higher concentration of people able to answer your question there. $\endgroup$
    – Ben Barber
    Mar 11, 2016 at 11:03
  • $\begingroup$ Thanks for this hint, but I think that I'm not at the level of the Polymath project. And the role of this project is not to answer questions. $\endgroup$
    – Panurge
    Mar 11, 2016 at 11:59

1 Answer 1

1
$\begingroup$

I do not know of a reference for your version. I provide some motivation for recasting your question into lattice terms.

Along similar lines is the following lower bound argument:

Assume there is a counterexample to Frankl's conjecture. Thus there is a collection F which contains its common nonempty union X. Since X is nonempty, there is an element z which occurs in X meaning it occurs in at least one member of F. Thus F (being a counterexample) has at least 2*1+1=3 members.

Since F has at least 3 members, two of the members are nonempty, and either one of them contains the other, or their union contains both. Either way, we find an element z in at least two members of F. So F contains at least 5 members.

Now we have at least 4 nonempty members of F to use. We assume without loss a nonempty member A of F contained in a nonempty member B of F. If third member C intersects A or A union C is distinct from B, we have z in A also in two other members of F. Otherwise B is the disjoint union of A and C and now we use D distinct from C to get D or D union A a third set containing either z or else B, C and D having a nonempty intersection. This means F has at least 7 members.

One can pursue this line with increasing complexity up to F having at least 13 members (I might remember/resurrect the argument from old notes); I am essentially looking at (semi-)lattices and trying to prove an equivalent inequality regarding the number of join-irreducible elements in the lattice. You might find some benefit in recasting your problem in lattice-theoretic terms. Poonen has shown such an equivalence in his 1990 REU paper, and by now the surveys on Frankl's conjecture should include this version and some progress on it.

I will look for my notes on derivations and post some related ideas, e.g. if union-closed finite F has k-many 2 sets then F has at least as many (-2)sets (shorthand for $|X|-2$), or F is one of finite and small number of exceptions.

Gerhard "Is Hobbling Down Memory Lane" Paseman, 2016.03.31.

$\endgroup$
2
  • $\begingroup$ One can streamline/sidestep the lower bound argument above with a similar result: If F is a reduced counterexample with union of n elements, then F has at least 4n-1 members. I remember browsing the library a year or so after I proved this and found it in an article of Giovanni Lo Faro, who had a mild extension of it. Gerhard "Didn't Strike A Cold Iron" Paseman, 2016.03.31. $\endgroup$ Mar 31, 2016 at 17:11
  • $\begingroup$ Thanks for your interest in my question. I first formulated it with a conjecture, but I now think that this conjecture has no value. I find it curious that in the first results I mentioned ($c =2$, $3$ or $4$), we have statements as "If $k$ is a natural number, if a union-closed family of sets has at least $f(c)k + c$ members with cardinality at least $k$, then this family has $c$ members whose intersection has cardinality at least $k$", with $f(c)k$ a linear function of $k$, and not something like $2^{k}$. But I didn't study the case $c=5$. $\endgroup$
    – Panurge
    Mar 31, 2016 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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