Family of subsets of $[n]$ and intersections

Question

Let $\mathcal{F}$ be a family of subsets of $[n] = \{1,\ldots,n\}$ such that for all $A,B,C \in \mathcal{F}$ at most $3$ out of $8$ triples $A\cap B \cap C$, $A \cap B^c \cap C$, $A \cap B \cap C^c$, $A \cap B^c \cap C^c$, $A^c \cap B \cap C$, $A^c \cap B^c \cap C$, $A^c \cap B \cap C^c$ and $A^c \cap B^c \cap C^c$ are non-empty (here $X^c$ is the complement of $X$). Prove that the size $|\mathcal{F}|$ is bounded from above by a constant independent of $n$.

Apart from considering the contrapositive (i.e. prove that if $|\mathcal{F}| > C_0$ then it contains $A,B,C$ with at least four non-empty intersection triples) I do not know what to do. I tried some extreme examples (such as $\mathcal{F}$ to consist of many pairwise disjoint sets) but do not see how to connect them for the general case.

Any help appreciated!

Answer 1

My answer is inspired by Ewan Delanoy’s that. He bounded size of $\mathcal F$ in terms of Ramsey numbers, showing that $|{\mathcal F}| \leq 2+R(2,R(4,4,3))=2+ R(4,4,3)$. The best known bounds for $R(4,4,3)$ are $55\le R(4,4,3)\le 77$, see [R, p. 39]. We shall show that $|\mathcal F|\le 14$.

Following Ewan Delanoy, given a subset $A$ of $[n]$ we put $A^+=A$, $A^-=A^c$ and let $A^{\pm}$ denotes $A$ or $A^c$. Subsets $A$ and $B$ of $[n]$ are independent, if all four intersections $A^{\pm}\cap B^{\pm}$ are nonempty. Assume that $|\mathcal F|\ge 3$.

Lemma. The family $\mathcal F$ does not contain independent members.

Proof. Suppose to the contrary that $A, B\in\mathcal F$ are independent and $C$ be an arbitrary member of $C$ distinct from $A$ and $B$. For any choice $^*, ^{**}$ of signs in $\pm$, a set $A^*\cap B^{**}$ is nonempty, so at least one of sets $A^*\cap B^{**}\cap C^+$ and $A^*\cap B^{**}\cap C^-$ is non-empty. So the family of sets of the form $A^\pm\cap B^\pm\cap C^\pm$ has at least four non-empty members, a contradiction. $\square$

Let a family $\mathcal F^*$ is obtained from family $\mathcal F\setminus\{\varnothing, [n]\} $ by replacing each member $A$ of $\mathcal F$ with $|A|>n/2$ by $A^c$. Then $|\mathcal F^*|\ge |{\mathcal F}|/2-1$ and $\mathcal F^*$ satisfies the question condition. Since $A^c\cap B^c$ is non-empty for each $A,B\in\mathcal F^*$, Lemma implies that any members of $\mathcal F^*$ are disjoint or one is contained in the other. It follows that any member of $\mathcal F^*$ contains a minimal element and minimal elements of $\mathcal F^*$ are pairwise disjoint. If $\mathcal F^*$ contains four minimal members $A$, $B$, $C$, and $D$ then sets $A\cap B^c\cap C^c=A$, $A^c\cap B\cap C^c=B$, $A^c\cap B^c\cap C=C$, and $A^c\cap B^c\cap C^c\supset D$ are non-empty, a contradiction. Thus $\mathcal F$ contains at most three minimal elements. Let $A$ be any of them. Suppose to the contrary that there exist distinct elements $B\supset A$ and $C\supset A$ of $\mathcal F^*\setminus \{A\}$. Since $B\cap C\supset A$ is non-empty, it follows that $B\subset C$ or $C\subset B$. Anyway, sets $A^c\cap B^c\cap C^c$, $A^c\cap B^c\cap C$, $A^c\cap B\cap C$, and $A\cap B\cap C$ are non-empty, a contradiction. Thus each minimal member of $\mathcal F^*$ is contained in at most one other member. Thus $|\mathcal F^*|\le 3\cdot 2=6$, and $|\mathcal F|\le 2(|\mathcal F^*|+1)\le 14$.

References

[R] Stanisław P. Radziszowski, Small Ramsey numbers. Dynamic Surveys. Electronic Journal of Combinatorics, revision #15: March 3, 2017.

Answer 2

Here is a proof that $|{\cal F}| \leq 2+R(2,R(4,4,3))$, where $R$ denotes Ramsey numbers.

Let $\cal E$ denote the subets of $[n]$ that are neither empty or full, and ${\cal F}'={\cal F}\cap{\cal E}={\cal F}\setminus \lbrace \emptyset, [n]\rbrace$. It will be convenient to use the notation $A^{-}$ for $A^c$ and define $A^{+}=A$ ; then $A^{\pm}$ means "$A$ or its complement". Say also that $A,B \subseteq [n]$ are independent if all four intersections $A^{\pm}\cap B^{\pm}$ are nonempty.

Step 1. $\cal F$ does not contain three mutually independent subsets.

Suppose that $A_1,A_2,A_3$ are mutually independent subsets in $\cal F$. Let $s_1$ and $s_2$ be signs in $\pm$. By independence, $A_1^{s_1}\cap A_2^{s_2}$ is nonempty, so at least one of $A_1^{s_1}\cap A_2^{s_2}\cap A_3^{-}$ and $A_1^{s_1}\cap A_2^{s_2}\cap A_3^{+}$ is non-empty. When $(s_1,s_2)$ varies over its four possible values, this already gives us four non-empty triple intersections, which contradicts the hypothesis on $\cal F$. QED

Step 2. ${\cal F}'$ does not contain an increasing sequence of three subsets.

Indeed, if $A_1 \subset A_2 \subset A_3$ is an increasing sequence of three subsets in $\cal E$, then the following four intersections are nonempty : $A_1^{-}\cap A_2^{-}\cap A_3^{-}$, $A_1^{-}\cap A_2^{-}\cap A_3^{+}$, $A_1^{-}\cap A_2^{+}\cap A_3^{+}$, $A_1^{+}\cap A_2^{+}\cap A_3^{+}$. QED

Step 3. ${\cal F}'$ does not contain four mutually disjoint subsets, or four subsets whose complements are mutually disjoint.

Indeed, if $A_k(1\leq k\leq 4)$ are four mutually disjoint subsets in $\cal E$, then the following four intersections are nonempty : $A_1^{+}\cap A_2^{-}\cap A_3^{-}$, $A_1^{-}\cap A_2^{+}\cap A_3^{-}$, $A_1^{+}\cap A_2^{-}\cap A_3^{-}$, $A_1^{-}\cap A_2^{-}\cap A_3^{-}$. QED

Step 4. $|{\cal F}'| \lt R(2,R(4,4,3))$.

Suppose by contradiction that $|{\cal F}'| \geq R(2,R(4,4,3))$. Then, by step 1, there is a ${\cal F}'' \subseteq {\cal F}'$ or cardinality at least $R(4,4,3)$ such that any $A,B \in {\cal F}''$ are never independent ; so there must be signs $s_A,s_B$ such that $A^{s_A}\cap B^{s_B}=\emptyset$. Color a pair $(A,B)$ blue if $(s_A,s_B)=(-,-)$, red if $(s_A,s_B)=(+,+)$, and yellow otherwise. Then, we must have either a blue or red four-set (ruled out by step 3), or a yellow three-set (ruled out by step 2). This finishes the proof.