Family of subsets of $[n]$ and intersections

combinatoricselementary-set-theoryextremal-combinatoricsramsey-theory

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!

Best Answer

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.

Related Question