Consider the set $[n]=\{1,2,\cdots,n\}$, and consider a family of subsets of this set, satisfying the following condition:
$$\forall \ i,j,k \in[n], i\ne j,j\ne k,i\ne k$$there exists a subset $A$ in this family such that $i,j\in A$, and $k \notin A$.
What is the minimum size of such a family? I very strongly feel it's equal to $O(log(n)^2)$, but am not able to prove this. Thanks in advance
I am turning Shengtong Zheng's commment into an snwer.
Using the probabilistic method, you can prove that $O(\log n)$ sets suffice.
Suppose we choose $m$ sets from $2^{[n]}$, uniformly at random. There are $O(n^3)$ ordered triples $(i,j,k)\in [n]^3$, and for each triple, the probability that there does not exist a chosen set which contains $i$ and $j$, but not $k$, is $(7/8)^m$. The expected number of "bad" triples is $$ n^3(7/8)^m $$ If you choose $m$ to be greater than $\log_{7/8}(n^{-3})\in O(\log n)$, then the expected number of bad triples is less than $1$, so there must a particular random choice with zero bad triples.
I do not know a constructive way to prove this result.