Let $\mathcal{A}$ be the family of all subsets of $U = [2n+1] = \{1,2,\ldots,2n,2n+1\}$ with size $n$, $n \ge 1$.
Let $\mathcal{F} \subseteq \mathcal{A}$ be a subfamily of $\mathcal{A}$ with the following properties:
- any $j \in U$ is contained in at least one set of $\mathcal{F}$;
- for any $\{i,j\} \subset U$ and such that $\{i,j\} \in F_1 \in \mathcal{F}$, there must exist $F_2 \in \mathcal{F}$, $F_2 \not= F_1$, such that $i \in F_2$ and $j \not\in F_2$, or otherwise $j \in F_2$ and $i \not\in F_2$.
I would like to prove that:
$$\vert \mathcal{F} \vert \ge n+2 \tag{1}$$
For example for $n=1$ an example of family of minimum size is $\mathcal{F} = \{\{1\},\{2\},\{3\}\}$, for $n=2$ $\mathcal{F} = \{\{1,2\},\{1,3\},\{1,4\},\{1,5\}\}$ or $\mathcal{F} = \{\{1,2\},\{2,3\},\{3,4\},\{4,5\}\}$, for $n=3$ $\mathcal{F} = \{\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{3,5,7\}\}$, and I think we cannot do better than that.
Any hint for proving or disproving $(1)$ or anyway find a lower bound for $\vert \mathcal{F} \vert$?
The correct bound should be more like $\log_2 n$, based on entropy considerations. Here is an explicit counterexample to $|\mathcal F| \ge n+2$. Let $n = 2^{k-1}$ be a power of $2$, so $U = [2^k+1]$. For $i = 1, \dots, k$ let $U_i$ be the set of all $x \in [2^k]$ such that $x-1$ has a $0$ in position $i$ in its binary expansion. Pick two further $n$-sets $U_{k+1}, U_{k+2}$ arbitrarily such that $2^{k} \in U_{k+1} \setminus U_{k+2}$ and $2^k+1 \in U_{k+2}$. It is easy to check this family works, so it is a counterexample provided $k+2 < 2^{k-1}+2$, i.e., $k \ge 3$.
Explicitly, for $k=3$, $n = 4$, $U=[9]$, the family is $$\mathcal F = \{\{1,3,5,7\}, \{1,2,5,6\}, \{1,2,3,4\}, \{1,2,3,8\}, \{1,2,3,9\}\}.$$