Set family $\mathcal{F}$ such that for all $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B $

Question

This question initially arose out of a question in asymptotic matroid theory. The matroid question has since been answered in a different way, but the extremal set theory question remains unanswered and may be of interest in its own right.

Question. Let $\mathcal{F}$ be a set family such that for all distinct sets $A,B,C \in \mathcal{F}$ both $A \cap B \not \subseteq C$ and $C \not \subseteq A \cup B$. Let $f(n)$ be the maximum size of such a set family on ground set $[n]$. What are the best known upper and lower bounds on $f(n)$?

Here is a simple argument that shows at least that $f(n)$ goes to infinity. Just draw a Venn diagram and make sure that all the cells contain a point.

I am hoping the extremal combinatorics people already know the answer. For example, there is this nice answer of Sergey Norin to this MO question on poisoned wines which describes the related concept of strongly union-free families (which just means that all pairwise unions are distinct).

My condition implies that $\mathcal{F}$ is both strongly union-free and strongly interection-free, but the converse does not hold. For example, the set family consisting of $\{1,2\}, \{2,3\}$, and $\{3,4\}$ is both strongly union-free and strongly interection-free, but does not satisfy my condition.

Answer 1

$f(n)$ grows exponentially in $n$ as may be seen by a simple probabilistic argument: choose $M$ subsets $A_1,\dots,A_M$ at random ($M$ to be specified later) independently. Then for given indices $i,j,k$ the probability that $A_i\cap A_j\subset A_k$ is $(7/8)^n$ (there should be no element which does not belong to $A_k$, but belongs to $A_i$ and to $A_j$), and the probability that $A_k\subset A_i\cup A_j$ is the same. So, if $2M(M-1)(M-2)(7/8)^n<1$, with positive probability there is no such an event. This may be further improved by applying Lovasz Local Lemma, since these events are not much dependent (each event depend on $O(M^2)$ other events only).

Answer 2

Just by the fact that your family needs to be both strongly union-free and intersection-free you can improve the upper-bound. First notice that a family $\mathcal{F} \subseteq 2^{[n]}$ is strongly union-free, iff $\overline{\mathcal{F}}= \{[n] \setminus A|A \in \mathcal{F}\}$ is strongly-intersection free. Let's denote by $f_k(n)$ The size of the largest strongly union- free k-uniform family $\mathcal{F}_k \subseteq {[n] \choose k}$, and by $g_k$ the same for strongly intersection-free. Then $g_k(n)=f_{n-k}(n)$. If you demand that your family is both strongly union-free and intersection-free, then the number of sets in the family in the $k$th layer is at most $\min(f_k(n),f_{n-k}(n))$. So the size of a family $\mathcal{F}$ fulfilling your constraints is at most $n\cdot \max_{k \in [n]}\min(f_k(n),f_{n-k}(n))$. Multiplying by $n$ of course becomes negligible as $n$ grows if you just want bounds on the base of the exponent.

If you look at this paper of Coppersmith and Shearer, they actually give a bound for $k$-uniform strongly union-free families, and then see for which $k$ this bound is largest, and multiply by $n$. I haven't done the calculations, but just because now you have the minimum of $f_k(n)$ and $f_{n-k}(n)$, their method should give you a better upper-bound.